目录
力扣300. 最长递增子序列
解析代码
力扣300. 最长递增子序列
300. 最长递增子序列
难度 中等
给你一个整数数组 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-10^4 <= nums[i] <= 10^4
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
}
};解析代码
以某个位置为结尾，结合题目要求，定义一个状态表示： dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度。
状态转移方程： 对于 dp[i] ，我们可以根据子序列的构成方式，进行分类讨论：
- 子序列长度为 1 ：此时 dp[i] = 1 ;（可以把dp表全初始化成1）
- 子序列长度大于 1 ： nums[i] 可以跟在前面任何一个数后面形成子序列。 设前面的某一个数的下标为 j ，其中 0 <= j <= i - 1 。 只要 nums[j] < nums[i] ， i 位置元素跟在 j 元素后面就可以形成递增序列，长度 为 dp[j] + 1 。 因此，仅需找到满足要求的最大的 dp[j] + 1 即可。
综上， dp[i] = max(dp[j] + 1, dp[i]) ，其中 0 <= j <= i - 1 && nums[j] < nums[i] 。
从左往右填表，最后返回dp表的最大值即可。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度
int n = nums.size(), ret = 1;
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[j] + 1, dp[i]);
}
ret = max(dp[i], ret);
}
return ret;
}
};