cdr 做网站页面/google play下载官方版

求数组中最长递增子序列
	写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。最长递增子序列Lis的长度是4；
	求一维数组中的最长递增子序列，也就是找一个标号的序列b[0],b[1],…,b[m](0 <= b[0] < b[1] < … < b[m] < N)，使得array[b[0]]<array[b[1]]<…<array[b[m]]。
	真正求Lis是有难度的，对于每一个长度都要保存一个Lis数组，而且长度还有相同的，这不仅仅是一个二维数组能够解决的，即便是求出Lis的长度，也难以求出了Lis。所以退而求其次先来求Lis的长度。
	OK，那如何求得Lis的长度呢？看看这个数组有啥性质，最优子结构，是的。整个数组的最优解包含除了-7之外的子数组的最优解。看起来好像可以用DP来做，不过不晓得她满足不满足重叠子问题性质。不过她首先满足了无后效性，在刚才的数组中，我们在找到4之后，并不关心4之前的值具体是怎样，因为它对找到6没有直接影响。因此，这个问题满足无后效性。

我们先来分析一下这个数组：1，-1，2，-3，4，-5，6，-7。
使用i来表示当前遍历的位置
       当i=1时，显然，最长的递增序列为（1），序列长度为1.
       当i=2是，由于-1<1。因此，必须丢弃第一个值后重新建立串。当前的递增序列为（-1），长度为1。
       当i=3时，由于2>1,2>-1。因此，最长的递增序列为（1,2）,(-1,2),长度为2。在这里，2前面是1还是-1对求出后面的递增序列没有直接影响。（但是在其它情况下可能有影响）
	从这个地方我们可以看出这个问题是具有重叠子问题性质的，因为当i=2,i=3的时候都要遍历i=1的值，看看-1>1?  2>1? 这个就是重叠子问题。所以我们有N个子问题，对于每一个子问题array[1--i]我们有i-1个选择，所以这个时候复杂度好像就是O(n^2)。
    假设在目标数组array[ ]的前i个元素中，最长递增子序列的长度为LIS[i]。
    如果array[i]大于array[k](k<i),那么第i个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列。与此同时array[i]本身至少可以构成一个长度为1的子序列。我们从前K个子问题中选出最长的，然后把array[i]放到他后面。
则状态转移方程
	LIS[i]=max{1,LIS[k]+1}   (array[i]>array[k],for any k < i)
这样的话代码就很好写了：

//求数组的最长的递增子序列LIS的值
int LisLength(int array[],int start,int end)
{int *Lis=new int[end-start+1];int i,j;int MaxLis=0;for(i=start;i<=end;i++){Lis[i]=1;for(j=start;j<i;j++){if(array[i]>array[j]&&Lis[j]+1>Lis[i])Lis[i]=Lis[j]+1;}}for(i=start;i<=end;i++){if(Lis[i]>MaxLis)MaxLis=Lis[i];}return MaxLis;
}

时间复杂度是O(n^2)，辅助空间是O(n)。
	还能继续优化吗？我们这样遍历是不是很麻烦？遍历比较遍历比较的。。我们可以统计前面所有的最长递增子序列的长度，将长度相同的最长递增子序列分到同一组中，并只记录长度相同的序列的最后一个值（也即是最大值）的最小值LisEndMin[length]。所以对于前i-1个值，我们没必要全部比较，只要和长度为m(1<=m<<maxlis)的子序列的最小值相互比较即可，此时如果array[i]大于这个最小值，这样就可以我们就可以把array[i]放到其后。如果此时长度大于了maxlis，则更新。
	而且更有意思的是我们发现LisEndMin数组具有递增的性质，这个很好证明的，反证法：假设长度为k的子序列最后一个值的最小值kmin大于长度为k+1的最后一个值的最小值(k+1)min，即kmin>(k+1)min。那么对于长度为k+1的子序列如果拿掉最后一个值(k+1)min，则变成长度为k的子序列，其最后一个值是kx，而且kx<(k+1)min。因为长度为k的子序列最后一个值的最小值是kmin，则kx>kmin。又因为kmin>(k+1)min，则kx>(k+1)min，与递增序列矛盾。得证。这个性质有啥好处呢？
	如果是递增的话，可和前面长度为m的子序列的LisEndMin相互比较的时候就不必一一比较，只要找到array[i]>LisEndMin[k]的k值即可。可以利用二分查找啊，在长度1和maxlis直接查找。
编码开始：

　　int LisLength(int array[],int start,int end){int *LisEndMin=new int[end-start+1];  //LisEndMin int MaxLis=1;LisEndMin[1]=array[start];int low,mid,high;for(int i=start+1;i<=end;i++){low=1;high=MaxLis;while(low<=high){mid=low+(high-low)/2;if(array[i]>LisEndMin[mid])low=mid+1;else if(array[i]<LisEndMin[mid])high=mid-1;}//正确的位置就是high+1if(high+1>MaxLis){MaxLis=high+1;}LisEndMin[high+1]=array[i];}return MaxLis;}

时间复杂度是O(nlgn)，辅助空间还是O(n)。
	代码是有问题的？问题在哪里？如果出现数组中出现相等的值，就会出现死循环的bug。如故数组中有相等的元素，对求Lis的长度有影响吗？没有一点影响，这个值就好像是多余的。比如有两个3，长度为k的LisEndMin=3，如果下个数组值也是3，那就会遍历到，可是有影响吗？没有。
	可是如何证明呢？如果之前的3前有x个数，那么之后的3得到的序列前面不会大于x个数，因为如果大于x的话，那么LisEndMin就不是3了，就不会碰到了。不大于x，那得到的最长序列就没有影响。对于之后的序列因为前面一个3足够了。举个例子琢磨一下。
	0 1 2 3 -2 -1 3 4 5 6 7 （3碰得到） 和0 1 2 3  -1 0 1 2 3 4 5 6 7（3碰不到）
修改代码

int LisLength(int array[],int start,int end)
{int *LisEndMin=new int[end-start+1];  //LisEndMin int MaxLis=1;LisEndMin[1]=array[start];int low,mid,high;for(int i=start+1;i<=end;i++){low=1;high=MaxLis;while(low<=high){mid=low+(high-low)/2;if(array[i]>LisEndMin[mid])low=mid+1;else if(array[i]<LisEndMin[mid])high=mid-1;elsebreak;}if(low>high){	//如果没有相等的元素则正常处理，如果出现相等的元素，不处理，没有一点影响。if(high+1>MaxLis){MaxLis=high+1;}LisEndMin[high+1]=array[i];	//正确的位置就是high+1}}return MaxLis;
}