求一个数列的最长非递增（递减）子序列
?
问题描述：给出一个数列，找出其中最长的单调递减（或递增）子序列。比如数列 4，2，6，3，1，5? 最长递增子数列为2,3,5??
??????????? 相似的问题：1求最大和的子序列
????????????????????????????? 2最大公共子串
????????????????????????????? 3最大公共子序列
? ? ? ? ? ? 注意：串与序列的关系，，串是连续的，而序列则不可以。。。
?
解决办法：在网上得到两种解法
解法一：
?
首先将这个序列进行排序，然后再求出已排序的和未排序的这两个数列最长公共子序列
?
解法二：就是用动态规划法来解决问题：
??????????? 我们假设原数列定义为数组a[]，然后定义一个数组b[i],表示以a[i]结尾的最长公共子序列的长度,只要求出所有的b[i]数组也就可以确定最长的公共子序列，
??????????? 那么我们根据已经求出的b[0]--b[i-1]，来求b[i]呢，，也就如何求出以a[i]结尾的最大公共子序列的长度呢，
??????????? 此时在a[0]-a[i-1]范围内，已经求出多个长度的公共子序列，且最大长度的一个序列的长度为s，这个序列的最后一个元素为t，那么
??????????? 1.如果a[i]<t ,那么当前最大子序列的长度为s+1，而且这个序列的最后一个元素就是a[i],即b[i]=s+1
??????????? 2.如果a[i]=t，那么这个子序列的长度不变，仍为s，b[i]=s;
??????????? 3.如果a[i]>t,这时候就会比较的麻烦了，因为a[i]不可能成为长度为s的最长公共子序列的最后一项了，然后与一个长度为s-1的公共子序列的最后一项进行比较。。直至小于某一个长度为s1的子序列的最后一个元素t1，
?
?????????????? 如果a[i]仍然大于t1，那么就继续向长度更小的子序列的最后一个元素进行比较，知道找到一个合适的子序列长度s2，那么此时b[i]=s2+1；如果a[i]比所有的以求子序列的最后一个元素都大话，那么最后就赋值b[i]=1;即以该元素为结尾的子序列长度为1.
????????????? 那么如何保存这些已经查找出来的子序列的最后一一个元素呢? ，我们定义一个数组c[],即c[i]就是代表长度为i的当前最长子序列的最后一个元素，我们最终的元素超找比较就是在c[]数组中进行的，b[i]最后可以用于最终的最长子序列的输出。
?
? ? ? ? ? ? ?? 按照上述的条件得到的c[i]肯定是单调递增或者递减的，如果采用二分查找的话那么时间复杂度为O(n*lgn)..
?
动态的转移公式为：
假设f(i)代表以a[i]结尾的最长单调自增子序列的长度：
??????? /??? f(i-1)+1 ? ?? ??????????????????????????????????? , a[i]>a[i-1]
f(i)= ---? f(i-1) ????????????????????????????????????????????? ,a[i]==a[i-1]
??????? \?? max(max({f(j)|a[i]<a[j],i>j}+1),1)? ,a[i]<a[i-1]
?
?
比如查找 4，2，6，3，1，5 的最长递减子数列过程如下：
最终的数组b[]={1,2,1,2,3,1}
数组c[]={-1,6,5,1,-1,-1,}
?
具体的算法如下：
void getArray(int *a,int length){int *b=new int[length]; //b[i]表示以a[i]结尾的最长递减子序列的长度int *c=new int[length];//数组c[i]表示长度为i的递减子序列的末尾值的最大值int s=1;//s表示目前为止最长单调序列的长度int k=1;for(int i=0;i<length;i++)//初始化b{b[i]=-1;} c[1]=a[0];for(int j=0;j<length;j++){ k=BinFind(c,s,a[j]); if(k>s) { s++; } c[k]=a[j]; b[j]=k;} print(a,b,s,length);//根据数组b[]来打印最长子序列}??
void print(int *a,int *c,int s,int length)//从后向前查找，并打印出来{int i=length; while(s>0){ while(c[i]!=s&&s>0) { if(i<=0) { break; } i--; } printf("%d ",a[i]); s=s-1; i--;}}?
?
?
下面在来说下几个相关的问题：
1.最大子序列问题
?? 就是求出连续的子序列的和最大，数组中有正数也有负数。。。。这个问题在之前已经描述过了。。
?? 就是遍历数组，保证序列的前面部分的和为大于零
?? 最后比较每个序列的和的大小并选择之
2.最长公共子串（LCS）
?
?? 这个问题主要是找出两个序列之中相同的最长的连续子串比如：abcad? abaad? 最长公共子串包括ad与ab
?
? 如何解决这个问题呢：
? 在网上见到一个比较新颖的解决方案：用矩阵的形式，如下：
?以一个二维数组来表示对应位置相同的位1，不同的为零
? ? b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
?
可以看见相同的子序列在一条斜线上都为1.所以最长公共子序列为ab，ba
在这种二位数组中寻找这种相同的元素也是比较困难的，，所以就修改到如下方式：
? b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
?
把斜线上的1加到加到最后一个元素位置上，但是考虑到算法的效率，这样会浪费很多无谓的空间，所以我们使用一维数组来描述二维数组：
?
定义两个一位数组，我们按行进行初始化，其中一个数组保存上一行的数据，另外一个数组保存当前行的数据，当前行的数据就是通过上一行来进行计算，最后找出最大的值
?
?
?
2.最长公共子串（LCS）
最常用的就是动态规划法：
?
?
?????????? /????? 0?????????????????????????????? if i<0 or j<0
c[i,j]=--- ???????? c[i-1,j-1]+1??????????????????? if i,j>=0 and xi=xj
??????? ?? \ ???? max(c[i,j-1],c[i-1,j]?????????? if i,j>=0 and xi≠xj
?
?
使用s[i][j]数列来保存c[i][j]使用上述哪种方式得到的，，，最后找出s[i][j]中所有位1为i,j（即是由i-1，j-1得到的c[i][j]）
?