AcWing 895. 最长上升子序列
原题链接
简单
作者:
我是java同学
,
2023-01-11 12:03:13
,
所有人可见
,
阅读 140
思路
- 集合:所有以i结尾的严格单调上升子序列的集合
- 状态计算
- 往不同的找——最后一个不同点,所有方案最后一个元素都是i自己,所以i不是最后一个不同点,所以找i-1(倒数第二个元素)
- 倒数第二个元素有可能是
a[0], a[1], a[2]...a[k]...a[i - 1]
- 第一类答案是确定的,就是
f[i] = 1
所有最小子序列长度都至少为1
- 不一定每一类都存在,当ak≥ai就不存在
#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int a[N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
int res = 0;
for (int i = 1; i <= n; i ++)
{
f[i] = 1;
for (int j = 1; j <= i; j ++)
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}