题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
样例
7
3 1 2 1 8 5 6
输出样例
4
算法1
(动态规划) $O(n^2)$
要是子序列最长,就得让第i个数接在前面i-1个数的最长子序列的后面
dp[i]=max(dp[1 ~ (i-1)] )+1
要找出前i-1个数的最长子序列长度就得遍历一遍前i个数
max(dp[1 ~ (i-1)] )
要保证子序列是上升的,就得让每一个接在子序列最后面的数要大于子序列最后面的那个数
dp[i]表示1~i个数中以i结尾的最长上升子序列的长度
时间复杂度 $O(n^2)$
C++ 代码
#include<iostream>
using namespace std;
const int N = 1010;
int a[N];
int n;
int dp[N];
int main()
{
cin>>n;
for(int i = 1 ; i <= n ; i ++) dp[i]=1,cin>>a[i];
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j < i ; j ++)
if(a[j]<a[i]) //确保该子序列是上升的
dp[i]=max(dp[i],dp[j]+1); //找出前i-1个数中最长上升子序列的长度 即 dp[j]+1
int res=dp[1];
for(int i =1 ; i <= n ; i ++) res=max(res,dp[i]);
cout<<res<<endl;
return 0;
}