问题描述

输入一串数字，或数组，如-5, 1, -3, -1, -2, 1, 4, 8, 9, 7，则该数组的最长递增子序列之一(注意，最长递增子序列有时候不止一个)为-5，-3，-1，1，4，8，9

思路一: 可以参考之前的博文

思路二： 具体思路参考，但他的代码有点问题，自己改了下

int dp_nlogn(int *data, int *auxData, int len)
{
	int seqLen = 1;
	int i, mid = 0, left = 1, right = 0;
	auxData[1] = data[1];
	for(i=2; i<=len; i++)
	{
		left = 1; 
		right = seqLen;
		while(left<=right)		//find a pos to insert
		{
			mid = (left + right)/2;
			if(auxData[mid]<data[i])
				left = mid + 1;
			else
				right = mid - 1;
		}
		if(left >= seqLen)  //curLen is logger than before
			auxData[left] = data[i]; //insert
		if(left>seqLen)	 
		{
			seqLen++;
		}
	}
	return seqLen;
}