最基础的最长上升子序列问题
这里用的是dp做法
定义f[i]为从1~i的所有上升子序列最大的长度
双重循环,以a[i]为最后一个数,枚举所有小于a[i]的数a[j]作为倒数第二个数,对于所有情况,最长子序列的长度即为f[i]=f[j]+1(f[j]为所有合法情况下的最大值)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N], a[N];
int n,ans;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)
{
f[i]=1;
for (int j = 1; j < i; j++)
{
if(a[j] < a[i])
f[i]=max(f[i],f[j]+1);
}
}
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
cout << ans << endl;
return 0;
}
标签:上升,895,int,序列,include,最长 From: https://www.cnblogs.com/lxl-233/p/16736498.html