DP14 最长上升子序列(一)
描述 给定一个长度为 n 的数组 arr,求它的最长严格上升子序列的长度。 所谓子序列,指一个数组删掉一些数(也可以不删)之后,形成的新数组。例如 [1,5,3,7,3] 数组,其子序列有:[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。 我们定义一个序列是 严格上升 的,当且仅当该序列不存在两个下标 iii 和 jjj 满足 i<ji<ji<j 且 arri≥arrjarr_i \geq arr_jarri≥arrj。 数据范围: 0≤n≤10000\leq n \leq 10000≤n≤1000 , ∣arri∣≤109 |arr_i| \le 10^9 \ ∣arri∣≤109 要求:时间复杂度 O(n2)O(n^2)O(n2), 空间复杂度 O(n)O(n)O(n) 输入描述: 第一行输入一个正整数 n ,表示数组的长度 第二行输入 n 个整数表示数组的每个元素。 输出描述: 输出最长严格上升子序列的长度 示例1 输入:
7 6 3 1 5 2 3 7
输出:
4
说明:
该数组最长上升子序列为 [1,2,3,7] ,长度为4
CPP参考:
#include<vector>
using namespace std;
class Solution{
public:
int lengthOfSeq(vector<int> &nums){
int result =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);
}
}
if(dp[i] > result){
result =dp[i];
}
}
return result;
}
};
int main(){
int n,val;
cin >>n;
vector<int> nums(n);
for (int i =0;i<n;i++){
cin >> val;
nums[i] = val;
}
Solution solu;
cout << solu.lengthOfSeq(nums) <<endl;
return 0;
}