最长非降子序列
给定序列a[1],a[2],…a[n],求出最长非降子序列的长度。
沿用求最少硬币的方法，如果我们考虑a[1],a[2],…a[i]的最长非降子序列，其中i
我们观察这个递推过程，同时思考我们求解这个问题的过程，其实如果求当前前i个元素的结果，就是将前面的子序列中，列尾不大于a[i]
的序列长度加1，如果列尾都大于a[i],那么就要将其置1，产生一个长度为1新的被求子序列。
根据上面的叙述，我们就可以很容易的写出代码来了。
<学习笔记>动态规划——初级入门
1
2
3
4
5
6
d(1)=1;序列5;子列为5
d(2)=1;序列5,3;子列为5或3
d(3)=2;序列5,3,4;子列为3,4
d(4)=3;序列5,3,4,8;子列为3,4,8
d(5)=3;序列5,3,4,8,6;子列为3,4,8
d(6)=3;序列5,3,4,8,6,7;子列为3,4,8或5,6,7
1
2
d(i)=max{1,d(j)+1};
//j<i;a[j]<=a[i];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main() {
int a[6] = {5,3,4,8,6,7};
int d[6];//存储过程中的序列长度；
int len = 1;//初始化长度为1；
for (int i = 0; i < 6; i++) {
d[i] = 1;//遍历到一个新的数字，那么假设它比前面的都小，初始化为1；
for (int j = 0; j < i; j++) {
if (a[j] <= a[i] && d[j] + 1 > d[i]) {
d[i] = d[j] + 1;
//从前面的子列中，找到那个列尾不大于a[i]的序列长度加1；
//有更长的就要继续更新；
}
}
if (d[i] > len) {
len = d[i];//找到更长的，就要更新；
}
}
cout << len << endl;
return 0;
}