算法导论15.4-6：最长单调递增子序列

参考资料：
《编程之美》2.16
http://blog.pfan.cn/rickone/13086.html
http://chriszeng87.iteye.com/blog/1054321

题目：给出一个O（nlogn)的算法，使之能够找出一个n个数的序列中最长的单调递增子序列。

O(n2)的比较好理解，没有仔细研究，研究了下O（nlogn)的解答和好多大神的分析才明白一些，发现玄妙无限呀~

对于序列S_n，考虑其长度为i的单调子列(1<=i<=m)。我们选取这些子列的最后一个元素的最小值。用L_i表示。则有L₁<=L₂<=…<=L_m。

序列a₁, a₂, …, a_n，从左至右扫描序列（可用二分法），对于每一个a_i，它可能

(1)    a_i<L₁，那么L₁=a_i

(2)    a_i>=L_m，那么L_m+1=a_i，m=m+1 (其中m是当前见到的最大的L下标)

(3)    L_s<=a_i<L_s+1，那么L_s+1=a_i

以上就是binarySrh中完成的主要任务。

　　数组a:1 3 5 2 3

1、修改后二分查找可得最长子序列的长度，得数组maxL:1 2 3。最终maxL的长度len即表示最长递增子序列的长度。这个我也只能理解，但不知道怎么证明。

2、如果要得到子序列的内容应该怎么做呢？

可以在遍历过程中，用mem数组记录数字j，j表示当前数字是长度为j的子序列的尾数字。遍历结束后，从后往前遍历mem即可得到长度为len, len-1, len-2, ... 1的所有子序列的结尾数字，这样就得到了最长递增子序列。

#include<iostream>
using namespace std;

int binarySrh( int *s, int len, int x ) #二分查找
{
	int left = 0,right = len-1, mid = (left+right)/2;
	while( left<=right )
	{
		if( x>s[mid] )	left = mid+1;
		else if( x<s[mid] ) right = mid-1;
		else return mid;
		mid = (left+right)/2;
	}
	cout << left << ' ';
	return left;
}

int main()
{
	int n = 10;//原始数组长度
	int a[10] = { 6, 1, 8, 3, 10, 11, 12, 13,  4, 5 };
	int maxL[10] = { 0 };//maxL[i]记录长度为i子序列的最小尾数
	int mem[10] = { 0 };//mem[i]表示以a[i]结尾的最长子序列

	maxL[0] = a[0];
	int len = 1;//length
	
	for( int i=1; i<n; i++ )
	{
		int j = binarySrh( maxL, len, a[i] );
		maxL[j] = a[i];
		mem[i] = j;
		if( ++j>len )
			len = j;
	}
	cout << "max length: " << len << endl;
	cout << "longest subsequence: ";
	int currMaxLen = len-1;
	for( int i=0; i<n; i++ )
		cout << mem[i] << " ";
	cout << endl;
	for( int i=9; i>=0&&currMaxLen>=0; i-- ) {
		if( mem[i]==currMaxLen ) {
			cout << a[i] << " "; //反向输出子序列
			currMaxLen--;
		}
	}
	cout << endl;
	return 0; 
}