最长递增子序列
题目链接:
题目描述:
给你一个整数数组
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
题目解析
在这个之前,我们说一下什么是子序列,我们可以将子序列看成数组的子集, 只不过这个子集有一定的要求,我们原本元素的相对位置是不能够改变的.例如下面的这样
这道题目我们求最长的子数组很相似,思路也是类似的.题目求的是我们数组的最长的子序列的长度.
算法原理
还是按照经验,我们这里仍旧按照之前的想法来.
- 以…为结尾
- 以…为开始
状态表示
根据题目分析,我们选择以…为结尾表示状态.那么我们的状态这样表示
dp[i]:表示以i位置为结尾,我们序列的最大长度状态转移方程
这里进行分析,我们这里存在两个选择.
- 一个元素单独作为子序列, 那么dp[i] = 1
- 和前面的元素打配合共同构成子序列, 那么此时我们需要遍历我们的前面的dp
解释一下我们第二个选择, 我们直到子序列是可以不连续的,那么此时我们就会出现这样的情况.
那么遍历我们前面的结果,此时我们需要找到前面的最大值.
初始化
初始化就简单了,我们这里直接初始为1可以,默认是第一个情况.
填表顺序
从左向由填.
返回值
题目要求的最大长度,那么我们这里使用一个变量保存最大就可以了.
编写代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int result = 0;
for(int i = 0; i < nums.size(); i++)
{
for(int j = i-1; j >=0; j--)
{
if(nums[j] < nums[i])
{
dp[i] = max(dp[j] + 1, dp[i]);
}
}
result = max(result, dp[i] );
}
return result;
}
};