题目：给定一个整数数组，求其中最长的严格递增子序列的长度。
注意子序列和子串的区别：
- 子序列不要求连续，相对顺序不变即可
- 子串要求是连续的串
思路：经典dp问题，定义dp[i]为以第i个数字结尾的最长上升子序列的长度，注意第i个数字被选中。
int lengthOfLIS(vector<int>& nums){
int n = nums.size();
if(n==0) return 0;
int dp[n]; // dp[i]表示以第i个数字结尾的最长上升子序列的长度
dp[0]=1;
int res = 1;
for(int i=1; i<n; i++){
dp[i]=1;
for(int j=0; j<i; j++){
if(nums[j]<nums[i]){
dp[i] = max(dp[i], dp[j]+1);
}
}
if(dp[i]>res) res=dp[i];
}
return res;
}
网友评论