C++ LeetCode300最长递增子序列

目录
  • LeetCode 300.最长递增子序列
  • 方法一：动态规划
  • AC代码
    • C++

LeetCode 300.最长递增子序列

力扣题目链接：leetcode.cn/problems/lo…

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

方法一：动态规划

AC代码

C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

以上就是C++ LeetCode300最长递增子序列的详细内容，更多关于C++ 最长递增子序列的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java C++题解leetcode902最大为N的数字组合数位DP

    目录 题目要求 阅读理解 思路:数位DP Java C++ 总结 题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int[digits.length]; for (int i = 0; i < digits.length; i++) nums[i] = Integer.parseIn

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • LIS 最长递增子序列 Java的简单实现

    今天遇到了一个求最长递增子序列的问题,看了之后就尝试着用Java实现了一下,关于什么是最长递增子序列,这里就不在赘述,可以百度或者Google之,以下为实现的代码: 说明:本段代码实现的功能为 (1)随机生成一个有10个元素的数组,然后输出它的最长递增子序列 (2)输出以其中某一个元素为结尾的最长递增子序列的长度 具体的实现思路在注释中已经详细表明了,比较简单,这里就不再赘述 import java.util.Arrays; import java.util.Random; public cla

  • C语言实现最长递增子序列问题的解决方法

    本文实例展示了C语言实现最长递增子序列问题的解决方法.分享给大家供大家参考.具体方法如下: 问题描述: 给定一个序列,找出其最长递增子序列长度. 比如 输入 1 3 7 5 输出 3 算法解决思路: 利用动态规划的思想,以序列的每个点最为最右端,找出每个点作为最右端时的子序列长度的最大值,即问题的求解.因此,在计算前面的每个点的时候,将其结果保存下来,后面的点与前面的点的数值进行比较,如果大,则在其长度基础上加1,并且找出所有可能情况下最长的保存为当前点的长度.形成递归. 具体实现代码如下: #

  • 求数组中最长递增子序列的解决方法

    存储扩展算法n2编程c 写一个时间复杂度尽可能低的程序,求一个一维数组(N个元素)中的最长递增子序列的长度.例如:在序列1,-1,2,-3,4,-5,6,-7中,其最长的递增子序列为1,2,4,6 或者 -1,2,4,6.(编程之美P198-202)分析与解法根据题目的要求,求一维数组中的最长递增子序列,也就是找一个标号的序列b[0],b[1],-,b[m](0 <= b[0] < b[1] < - < b[m] < N),使得array[b[0]]<array[b[1

  • C++计算整数序列的最长递增子序列的长度操作

    给定一个整数序列,计算其中的最长递增子序列的长度,这是一个典型的动态规划的算法. 比如8个整数的序列 186 186 150 200 160 130 197 200,最长递增子序列是 150 160 197 200, 长度为4. 想要解决此问题,可以把这个大问题分解为小问题,依次考虑每个数,计算出包含该数数和该数之前的所有数的最长递增子序列的长度,计算出的长度值作为该数的对应值记录下来,最后可以得到这8个数对应的长度值序列,也是8个数,找到这8个数中的最大值就是所有书的最长递增子序列的长度. 或

  • Java算法之最长公共子序列问题(LCS)实例分析

    Java算法之最长公共子序列问题(LCS)实例分析

    本文实例讲述了Java算法之最长公共子序列问题(LCS).分享给大家供大家参考,具体如下: 问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X= { x1, x2,-, xm},则另一序列Z= {z1, z2,-, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,-, ik},使得对于所有j=1,2,-,k有 Xij=Zj.例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,

  • SQL计算字符串中最大的递增子序列的方法

    SQL计算字符串中最大的递增子序列的方法

    求字符串中最大的递增子序列 数据库环境:SQL SERVER 2005 如题,求字符串"abcbklmnodfghijkmer"中最大的递增子序列.这个字符串有点特别, 只由26个小写字母a-z组成. 大概思路如下: 1.将字符串转到一列存储,并生成行号 2.设置一个递增计数器列,默认为1,比较上下行的字符,如果在字典中的顺序是递增, 则计数器加1,否则,计数器置1 3.找出计数器最大的数及对应的行号,根据这2个数截取字符串 思路有了,下面直接贴代码 DECLARE @vtext VA

  • Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情

  • 利用C++实现最长公共子序列与最长公共子串

    利用C++实现最长公共子序列与最长公共子串

    一.问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列.最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个.子串是要求更严格的一种子序列,要求在母串中连续地出现.在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共

  • Java最长公共子序列示例源码

    最长公共子序列(Longest Common Subsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列.其实说到最长公共子序列,还有一个要提到的是最长公共子串(Longest Common Substring),它指的是两个字符串中的最长公共子串,要求子串一定连续.关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容. 之前看过一个LCS算法的实现过程,觉得太过繁琐.自己写了一个比较简单的,此处仅仅介绍实现过程. 程序代码测试通过,需要的童鞋

随机推荐