1.问题描述：

求一个正整数序列的最长单调自增子序列，子序列不要求是连续的。例如

Input：5

5 2 4 3 1

Output：2

 

2. 算法复杂度是O(N*N)

确定状态转移方程，设f[i]是以a[i]为结尾的最大值的子序列的长度，那么\[\max \{ f[i]\} \]的最大值就是要的结果。

所以转移方程为：

\[f(i) = \max \{ f(x)|x < i,{a_i} > {a_x}\}  + 1\]

所以代码可以为：

void main(void){	int arr[] = {10,4,20,10,15,13};	int dist[6];	int path[6];	int num = 6;	int i = 0;	for(i = 0; i < 6; i++)	{		dist[i] = 0;		//-1表示前面没有元素了，用于回头求解的时候定界		path[i] = -1;	}	for(i = 0; i < num; i++)	{		int temp = 0;		int index = -1;		for(int j = i - 1; j >= 0; j--)		{			if(arr[i] > arr[j] && dist[j] > temp)			{				temp = dist[j];				index = j;			}//if		}//for		dist[i] = temp + 1;		path[i] = index;	}//for	//找到最大的那个值	int max = 0;	int maxIndex = -1;	for(int m = 0; m < num; m++)	{		if(dist[m] > max)		{			max = dist[m];			maxIndex = m;		}	}//for	printf("最长单曾子序列的长度是%d.\n", max);	while(path[maxIndex] != -1)	{		printf("%d->", arr[maxIndex]);		maxIndex = path[maxIndex];	}//while	printf("%d\n", arr[maxIndex]);}

　　很显然时间复杂度是O(N*N)，那么有没有更快的算法呢？按照正常的思路更快的复杂度应该就是O(N*logN)，那么就要涉及到二分了。

 

3. 算法复杂度是O(N*logN)

建立一个辅助数组c[n]，c[i]=j存储的是子序列长度为i的序列最后一个值j（实际上子序列长度为i的子序列有多个，要的是子序列最后一个值最小的）。

这时要遍历要处理的数组arr[n]。

for(i=0;i

请看一下上面的例子实际执行的情况：C数组变化的情况

-1 5-1 2-1 2 4-1 1 2-1 1 4-1 1 3

arr数组遍历是从前往后的，处理arr[i-1]时arr[i]以及后面的值肯定还没有处理，前面的值都处理过了，看c数组，每个arr数组中的值和c数组中值进行比较，找到合适的位置插入（若插入到c数组的末尾，那么就属于最长递增子序列长度加1，实际上c数组的长度就是最后的最长单调递增子序列的长度。），否则这就替换掉了c数组中原来位置存储的值，这种替换是有意义的，主要是为了后来的arr数组中的值计算dist用（dist[i]中保存的是以arr[i]为最后一个元素的最长单调递增子序列。）好处是若arr[i] <arr[j],dist[i]=dist[j]，那么在c中肯定要保存arr[i]呀！！（注意c数组的下标代表的是子序列的长度，c数组中的值也是按递增顺序排列的。这才可能用二分呢，亲）。和O(N*N)的主要区别就是巧妙的借用了c数组，本题的关键就是理解c数组的意义。可以手动模拟一下算法执行的步骤，重要模拟c和b数组的变化情况。c数组是以-1位开头的有序的递增数列。

 

下面给出完整的算法

 

#include 
     
      #define MAX 100void fill(int a[], int len);int find(int a[], int cLastIndex, int x);int main(){	int arr[MAX] = {0};	int dist[MAX] = {0};	int c[MAX];	int num;	//原始数字序列的长度	int i = 0;	freopen("in.txt", "r", stdin);	freopen("out.txt", "w", stdout);	printf("读取数字序列长度...\n");	scanf("%d", &num);	printf("读取数字序列...\n");	for(i = 0; i < num; i++)	{		scanf("%d", &arr[i]);	}//for	//初始化c数组，长度是arr数组+1	fill(c, num + 1);	c[0] = -1;	//使得递增数列的最小值为-1		for(i = 0; i < num; i++)	{		int j = find(c, i + 1, arr[i]);		c[j] = arr[i];		dist[i] = j;	}//for	//c数组中保存的就是结果的数字序列，打印一下	i = 1;	while(c[i] != 100)	{		printf("%d ", c[i]);		i++;	}	fclose(stdin);	fclose(stdout);	return 0;}void fill(int a[], int len){	for(int i = 0; i < len; i++)	{		a[i] = 100;	这就是一个初始化，无所谓，目的就是是这个数列递增	}}//在数组a中，寻找数字x//如果存在返回其下表，如果不存在返回其该插入的位置，会覆盖掉原来在该位置的数字int find(int a[], int cLastIndex, int x){	int left = 0;	int right = cLastIndex;	int mid = (left + right) / 2;	while(left <= right)	{		if(x > a[mid])		{			left = mid + 1;		}		else if(x < a[mid])		{			right = mid - 1;		}		else		{			return mid;		}		mid = (left + right) / 2;	}//while	return left;}//find()
     

　　通过上面的代码可以看到，其实dist数组根本没有用到，只用c数组就能求解问题，其实这种算法已经不是动态规划了，虽然它的时间复杂度比动态规划的要好。这个算法的根本思想就是想到一个c数组，这个有序递增的数组用来存储最长的子序列。确实是一种很不错的手法。

测试数据：

610 4 20 10 15 13

运行结果：

读取数字序列长度...读取数字序列...4 10 13