问题描述
对于一串数A={a1a2a3…an}，它的子序列为S={s1s2s3…sn}，满足{s1<s2<s3<…<sm}。求A的最长子序列的长度。
动态规划法
算法描述：
设数串的长度为n，L[i]为以第i个数为末尾的最长上升子序列的长度，a[i]为数串的第i个数。
L[i]的计算方法为：从前i-1个数中找出满足a[j]<a[i]（1<=j<i）条件的最大的L[j]，L[i]等于L[j]+1。
动归表达式：
代码实现：
- int LIS(int a[], int n)
- {
- int len[MAXSIZE];
- int i, j;
- int maxlen = 0;
-
- for (i = 1; i <= n; i++)
- {
- len[i] = 0;
-
- for (j = i-1; j >= 1; j--)
- {
- if (a[j] < a[i] && len[j] > len[i])
- {
- len[i] = len[j];
- }
- }
- len[i]++;
-
- if (len[i] > maxlen)
- {
- maxlen = len[i];
- }
- }
- return maxlen;
- }
上述算法的时间复杂度为O(n2)。
最长上升子序列
原文：http://www.cnblogs.com/Alex0111/p/4604549.html
