最长上升子序列（LIS）及其优化O（nlongn）

1.求最长上升子序列：

1.1 思路：用一个数组d记录到i位置的最长上升子序列d(i)，那么第j个位置上的值就可以用前j-1个值来更新，时间复杂度O（N^2)。

1.2 代码实例：

int d[100005];
int LIS(int A[],int n){
	memset(d,0,sizeof d);
	for(int i = 0;i < n;i++){
		d[i] = 1;
		for(int j = 0;j < i;j++){
			if(A[i] >= A[j])	d[i] = max(d[i],d[j]+1);
		}
	}
//	cout << d[n-1] << endl;
	return d[n-1];
}

2.优化：

1.1 思路：这次用len来表示当前上升子序列的长度，d数组来存放对应LIS长度的最小末尾。

• 例如：A = {1 5 3 4 7}，那么d[1] = 1,d[2] = 3,d[3] = 4, d[4] = 7。（其中d[1]LIS长度为1，d[3]LIS长度为3，以此类推）

对上述例子详解：

1. 从i = 0开始，A[0] = 1,将它放在d[1],此时d[1] = 1，len = 1；
2. i = 1时A[1] = 5，5大于d数组最后一个数d[1] = 1，将5放在d[1]的后面，也就是d[2]，于是d[2] = 5，len=2；
3. i = 2时A[2] = 3，从d数组中找到小于3的最大数，是d[1] = 1，那么就把3放在d[1]后面，于是d[2] = 3；
4. i = 3,A[3] = 4，同2，放在d[3]，len= 3；
5. i = 4,A[4] = 7，同2，放在d[4]，len = 4。

1.2 代码实例：

int d[100005];
int b_search(int x,int s,int e){
	while(s < e){
		int mid = s+(e-s)/2;
		if(d[mid] >= x)	e = mid;
		else s = mid+1;
	}
	return s;
}
int LIS(int A[],int n){
	memset(d,0,sizeof d);
	int len = 1;
	d[1] = A[0];
	for(int i = 1;i < n;i++){
		if(A[i] >= d[len])	d[++len] = A[i];
		else{
			int p = b_search(A[i],1,len);
			d[p] = A[i];
		}
	}
//	for(int i = 0;i < len;i++)	cout << d[i+1]<<" ";
	return len;
}