学步园

题目描述：

给定一个整型数组， 求这个数组的最长严格递增子序列的长度。 譬如序列1 2 2 4 3 的最长严格递增子序列为1，2，4或1，2，3.他们的长度为3。

输入：

输入可能包含多个测试案例。
对于每个测试案例，输入的第一行为一个整数n(1<=n<=100000)：代表将要输入的序列长度
输入的第二行包括n个整数，代表这个数组中的数字。整数均在int范围内。

输出：

对于每个测试案例，输出其最长严格递增子序列长度。

样例输入：

4
4 2 1 3
5
1 1 1 1 1

样例输出：

2
1

本题的主要解题思路请参考：http://blog.csdn.net/dangwenliang/article/details/5728363和http://www.cnblogs.com/liyongmou/archive/2010/07/11/1775341.html。

#include <stdio.h>

#define MAX 100000
#define VMAX 100001
#define MIN (-2147483647 - 1)

int BSearch (int MaxV[], int start, int end, int key){
	int mid;

	while (start <= end){
		mid = start + ((end - start) >> 1);
		if (MaxV[mid] < key){
			start = mid + 1;
		}
		else if (MaxV[mid] > key){
			end = mid - 1;
		}
		else
			return mid;
	}
	return start;
}

int LIS (int data[], int n){
	int MaxV[VMAX];
	MaxV[1] = data[0];
	MaxV[0] = MIN;

	int nMaxLIS = 1;
	int i, j;
	for (i=1; i<n; ++i){
		j = BSearch (MaxV, 0, nMaxLIS, data[i]);
		if (j > nMaxLIS){
			nMaxLIS = j;
			MaxV[j] = data[i];
		}
		else if (MaxV[j-1] < data[i] && data[i] < MaxV[j]){
			MaxV[j] = data[i];
		}
	}
	return nMaxLIS;
}

int main(void){
	int data[MAX];
	int n;
	int i;

	while (scanf ("%d", &n) != EOF){
		for (i=0; i<n; ++i){
			scanf ("%d", &data[i]);
		}
		printf ("%d\n", LIS (data, n));
	}

	return 0;
}