AcWing 895. 最长上升子序列
原题链接
简单
作者:
永远热爱
,
2021-05-12 09:33:59
,
所有人可见
,
阅读 323
#include<iostream>
using namespace std;
const int N=1100;
int dp[N],a[N],g[N];
// 1 找定义 dp[i] 就是指的是前i个数数值严格单调递增的子序列的长度最长是多少
// 2 找关系 dp[i]=max(dp[1],dp[2],dp[3],.....dp[i-1])+1;
// 3 初始化 dp[i]=1; 如果一个递增的数列都没有 那么dp[i]=1; 因为他本身就算一个数
// dp[0]=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]; // 3 1 2 3
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
{
// 关于为什么要max 比如 1 2 5 1 7 dp[3]=3,dp[4]=1;
// 1<7 dp[5]=max(dp[5],dp[4]+1)=max(4,2)那肯定是4 所以要一个max
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int k=1;
for(int i=1;i<=n;i++)
{
if(dp[k]<dp[i])
k=i;
}
cout<<dp[k]<<endl;
return 0;
}