《编程之美》里有个题目是要求数组中最长递增子序列，在CSDN上看到的题目是数组中的最长递减子序列。题目如下：
求一个数组的最长递减子序列
比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
求一个数组的最长递增子序列
比如{1，-1，2，-3，4，-5，6，-7}的最长递减子序列为{1，2，4，3，6}
最长递增序列和最长递减子序列的解法是一样的，最不济，也可以先revert，求完再revert一次。
首先我们得搞清一个范围问题，虽然我们要的是一个最大值，但是是不是他是可以递推的呢，就是我只保存一个最大值，然后不断增加这个值，直觉上看应该是不太现实的，比如：12345-101234，我们数到5时最大值是5，但往后看时，都比5小，不能增加最大值，但事实上是最大值是6，如果我们受限于前面求的的一个最大值，就会产生错误的结果，也许你可以说，我就是保存一个值，没到一个点我就重新算新的最大值，虽然牺牲一点计算，但是我就想只有一个变量，有思路吗？如果没有就换个思路吧。既然递推困难，我们就把各个备选值都列出来，然后找出那个最大的，那哪些是备选值呢？其实以任意元素为终点的递增序列都是合法的candidate。
解法1：
如同上面的分析，考虑一个序列x0, x1,x2,… xn-1, xn。我们想知道以每个元素为终点的最长递增子序列的长度，令temp[i]表示以xi为终点的递增序列的长度，假设已经知道了temp[0]-temp[n-1]，那如何求temp[n]呢？如果xi
#include
usingnamespacestd;
intLIS(intarr[],intn)
{
int*temp=newint[n];//存放当前遍历位置最长序列for(inti=0;i
{
temp[i]=1;//初始化默认长度for(intj=0;j
//当前值array[i]跟已经遍历的值比较，//大于已经遍历的值且已知递增序列+1大于当前值则更新当前最长递增序列值if(arr[i]>arr[j]&&temp[j]+1>temp[i])
{
temp[i]=temp[j]+1;
}
}
}
intmax=temp[0];
for(intk=0;k
if(max
max=temp[k];
}
returnmax;
}
intmain()
{
intarr[]={1,-1,2,-3,4,-5,6,-7};
intresult=LIS(arr,8);
cout<
}
解法2：
解法1中用一个数组存储以各个元素为终点的最长递增子序列的长度，然后每新增加一个元素时，就遍历前面所有的元素，来知道新元素的temp值，复杂度是O(n2)。每个元素都得求一遍，这是毋庸置疑的，求法上能不能优化一下呢？那就把前面元素和其最长递增序列值排个序吧，当求xn的最长递增序列时，找到前面的序列中比xn小的最大值(可能有多个，位置不同时，序列长度也会不一样)，然后加一个1就可以了。代码如下：
解法3：
相类似于解法2，我们不是把序列排序，而是按照序列长度排序，并记录特定长度序列下终点元素的最小值，然后用xn跟这些最小值比，当然我们可以用折半查找，代码如下：
#include
usingnamespacestd;
intLIS(intarray[],intn)
{
inttemp[n];//存放当前遍历位置最长序列intMaxV[n];//最长子序列中最大值之间的最小值MaxV[1]=array[0];//初始序列长度为1的子序列中最大值的最小值MaxV[0]=-9999;//边界值
for(inti=0;i
{
temp[i]=1;//初始化默认长度}
intnMaxLis=1;
intj;
for(inti=0;i
{
for(j=nMaxLis;j>=0;--j)//找出前面最长的序列{
if(array[i]>MaxV[j])//当前值大于长度为j的子序列中最大值之间的最小值{
temp[i]=j+1;
break;
}
}
if(temp[i]>nMaxLis)//在最长子序列时停止(这时只有一个最长的){
cout<
nMaxLis=temp[i];
MaxV[temp[i]]=array[i];
}
elseif(MaxV[j]
{
MaxV[j+1]=array[i];
}
}
returnnMaxLis;
}
intmain()
{
intarr[]={1,-1,2,-3,4,-5,6,-7};
intresult=LIS(arr,8);
cout<
}
解法4：
还记得我们关于序列的一个经典问题：最长公共子序列。是不是可以转化呢？将原序列排序，并和原序列求最长公共子序列，求得的最长公共子序列长度就是最长递增子序列的长度。
Reference
