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

最长单调递增子序列定义：

问题描述：

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

输入

第1个整数n(0<n<100),表示后面有n个数据，全部为整数。

输出

输出最长单调递增子序列的长度；

样例输入

8

65 158 170 155 239 300 207 389

样例输出

6

算法描述：

计算最长递增子序列的动态规划算法

#define NUM 100int a[NUM];//序列Lint LIS_n2(int n) {int b[NUM]={0};//辅助数组bint i,j;b[1] = 1;int max = 0;//数组b的最大值for (i=2;i<=n; i++) {int k = 0;for (j=1; j<i; j++)//0~i-1之间，b的最大值if (a[j]<=a[i] && k<b[j]) k=b[j];b[i] = k+1;if (max<b[i]) max=b[i];}return max;}