动态规划——最长上升子序列
最长上升子序列（Longest increasing subsequence）
问题描述 对于一串数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 BSearch(int a[], int n, int t){int low = 1;int high = n;while (low <= high){int mid = (low + high) / 2;if (t == a[mid]){return mid;}else if (t > a[mid]){low = mid + 1;}else{high = mid - 1;}}return low;}int LIS_BSearch(int a[], int m[], int n){int maxlen = 1;//最长上升子序列的长度m[maxlen] = a[1];int i;for (i = 2; i <= n; i++){if (a[i] > m[maxlen]){m[++maxlen] = a[i];}else{//返回小于a[i]的最大值的位置pint p = BSearch(m, maxlen, a[i]);m[p] = a[i];}}return maxlen;}
改进后的算法时间复杂度为O(nlogn)。