A52019. 最长上升子序列
填空题
困难
知识点
题目描述
最长上升子序列
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入
[10,9,2,5,3,7,101,18]
输出
4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
参考答案
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()<=1) {
return nums.size() ;
}
int ans = 1;
vector<int> dp(nums.size(),1) ;
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) ;
}
}
}
for(int i=0; i<nums.size(); i++) {
ans = max(ans,dp[i]) ;
}
return ans ;
}
};
上一题
下一题