单调递增最长子序列（动态规划）

7-1 单调递增最长子序列 (20分)

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

输入格式:

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

输出格式:

最长单调递增子序列的长度

输入样例:

在这里给出一组输入。例如：

5

1 3 5 2 9

输出样例:

在这里给出相应的输出。例如：

4

采用的是动态规划，可以划分为若干不独立子问题

·使用一维数组b[n]计算，即b[i]存放a[0]-a[i]的最长单调递增子序列长度

例如

a[i] 1 3 5 2 9

b[i] 1 2 3 2 4

对于a[3]=2来说， b[3]=2，即单调递增最长子序列长度为2，即 1 2

a[4]=9 ，b[4]=4，长度为4，即1 3 5 9

#include <iostream>using namespace std;int a[100001], b[100001];int max(int n, int a[], int b[]){for(int i=1; i<n; i++){for(int j=0; j<i; j++){//这个循环是从a[0]到 a[i] 这段数里每个数的最长长度 if(a[i]>a[j] && b[j]>b[i]-1){// b[j]>b[i]-1 判断应不应该加入这个子序列 b[i]=b[j]+1; }}}int m = b[0];for(int i=1; i<n; i++){//挑选最大的数，就是可以组成的最大长度 if(b[i]>m) m=b[i];}return m;}int main(){int n;cin >> n;for(int i=0; i< n; i++){cin >> a[i];b[i]=1; //对于一个序列，最少包含一个数，即使这个数前面的数都比他大 }cout << max(n, a, b);}

if(a[i]>a[j] && b[j]>b[i]-1){ // b[j]>b[i]-1 判断应不应该加入这个子序列

例如上例

a[i] 1 3 5 2 9

b[i] 1 2 3 2 4

当i=4，a[3]<a[4] 但是不能加入，因为从头检测的时候相当于1 3 5已经加入这个包含9的子序列了，如果要加入2，子序列变成1 2 9 明显变短

b[i]-1就是不包括a[i]时这个子序列的长度，如果b[j]比它更大，那a[i]加入a[j]所在子序列，b[i]在b[j]的基础上加1