题目:
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解析:
这其实是一个递归题目,dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度,从0~i-1找到小于当前值的值同时其dp又是所有满足这个情况里面最大的,只需要将这个的dp+1即是当前值的最大上升子序列长度。
代码:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 1) return 1;
vector<int>dp(nums.size(),1);
int result = 0;
for(int i = 1; i < nums.size(); ++i){
for(int j = 0; j < i; ++j){
if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j]+1);
}
result = dp[i] > result?dp[i]:result;
//if (dp[i] > result) result = dp[i]; // 取长的子序列
}
return result;
}
};