当前位置 博文首页 > ljmhxs的博客：最长上升子序列（动态规划）
设有由n个不相同的整数组成的数列，记为b[1],b[2]...b[n]
若存在i[1]<i[2]<...<i[e]且有b[i[1]]<b[i[2]]<...<b[i[e]]，则称为长度为e的上升子序列。程序要求，当输入原数列之后，求出最长的上升子序列。
其中13,16,18,19,21,22,63就是一个长度为7的不下降序列。
同时也也有7,9,16,18,19,21,22,63.组成的长度为8的不下降序列。
输入第一行n，表示数列的长度
第二行n个正整数用空格隔开
共两行，一行为一个整数表示最长不下降子序列的长度。如样例格式；
第二行，输出最长不下降子序列，如样例格式；
（每个数字之间两个空格）
对于所有的数据：n<=10^4，所有b[i]均在32位有符号整数范围内
于是在睡梦中了，笑死n<=10^4要是按这样写：
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int k=i;k<=j;k++)
}
}时间复杂度是O(n^3)，当n为1000时，即10000^3=10^12，用脚趾头想想也超时了。
我们用动态规划来写这道题（没事，学过基础语法的人保证能看懂）：
#include <bits/stdc++.h>
using namespace std;
const int s = (int)1e4 + 10;
int a[s], f[s], g[s], n, ans, x;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i]; //输入
for (int i = n; i >= 1; i--) { //为简便，从后到前循环
f[i] = 1, g[i] = i; //标记
for (int j = i + 1; j <= n; j++) { //从i开始，到n结束
if (a[i] < a[j] && f[j] + 1 > f[i]) { //如果前面的数小于后面的数并且方案内数量+1大于前一个方案内数量，就执行下列语句
f[i] = f[j] + 1; //f数组指方案内数量
g[i] = j; //g数组指最大方案数中每个数位置
}
}
}
for (int i = 1; i <= n; i++) {
if (f[i] > ans) { //寻找最大方案数量，执行下列语句
ans = f[i];
x = i;
}
}
cout << "Max=" << ans << endl; //输出最大方案数量
while (1) { //输出最大方案内所有的数
cout << a[x] << " ";
if (g[x] == x) { //终止条件
break;
}
x = g[x];
}
return 0;
}点赞你要亮，关注干得漂亮
不关注点赞你就别走（好像我也留不住）
那就要个点赞吧（要求不大吧）
每天必须日更！！
