题目描述
有长度为N的序列:
A1 A2 …..An
求最长不下降子序列：Ai1,Ai2,,,,,Aik, 其中ai1<=ai2<=.....<=aik
求最长不下降子序列的长度
输入
从文件 seq.in 中读入数据。
第一行，n;
第二行，n 个数。
输出
输出到文件 seq.out 中。
最长不下降子序列的长度
样例输入 复制
11
1 3 6 3 4 7 5 7 6 7 8
样例输出 复制
8
如：1 3 3 4 5 6 7 8
正片开始！
首先，按照国际惯例，这是一道十分淼的题（没做出的同学请冷静），本蒟蒻也才花了0.5小时才解出来
题意为：求最长不下降子序列的长度 ，注意：并不用连续
好，这很明显就是一道DP题，我们可以推导一下
首先，我们可以画一个图
数组代表我们的输入，DP代表从第i个数开始，向后的最长不下降子序列，dp要初始化为1哦
然后呢，我们枚举i个数，看他的最长不下降子序列， 即
OK，理论存存存在！，开始Code
#include <bits/stdc++.h>
using namespace std;
int n;
int a[999999], dp[999999];
int cnt = 1, ans;
int main() {
// freopen("seq.in","r",stdin);
// freopen("seq.out","w",stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) dp[i] = 1;//初始化
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] <= a[i])
dp[i] = max(dp[j] + 1, dp[i]);//状态转移方程
}
ans = max(dp[i], ans);//得出最长子序列
}
cout << ans ;
return 0;
}