单调递增最长子序列
时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
- 求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4- 输入
- 第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000 - 输出
- 输出字符串的最长递增子序列的长度
- 样例输入
-
3 aaa ababc abklmncdefg
- 样例输出
-
1 3 7
之前有转过一篇博文，是用的动态规划做的，不过该方法时间复杂度为O(n^2)。
然而还有另一种方法，贪心+二分查找：
(摘之:http://www.cnblogs.com/liyongmou/archive/2010/07/11/1775341.html)
开辟一个栈，每次取栈顶元素s和读到的元素a做比较，如果a>s， 则加入栈；如果a<s，则二分查找栈中的比a大的第1个数，并替换。 最后序列长度为栈的长度。
这也是很好理解的，对x和y，如果x<y且E[y]<E[x],用E[y]替换E[x],此时的最长序列长度没有改变但序列Q的''潜力''增大。
举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，则用3替换5，得到栈中元素为1，3，8， 再读6，用6替换8，得到1，3，6，再读7，得到最终栈为1，3，6，7 ，最长递增子序列为长度4。
第二种方法的时间复杂度平均为O(nlogn)。
方法一：动态规划
01.#include
<iostream>02.#include
<string>03.using namespace std;04. 05.int dp[10002];06. 07.int main()08.{09.int t;10.cin>>t;11.while(t--)12.{13.string
s;14.cin>>s;15.int len=s.size();16.for(int i=0;i<len;i++)17.dp[i]=1;18.int maxlen=1;19.for(int i=1;i<len;i++)20.{21.int max=0;22.for(int j=0;j<i;j++)23.{24.if(s[j]<s[i]&&dp[j]>max)25.max=dp[j];26.}27.dp[i]=max+1;28.if(dp[i]>maxlen)29.maxlen=dp[i];30.}31.cout<<maxlen<<endl;32.}33.return 0;34.}
方法二：贪心+二分查找
01.#include
<iostream>02.#include
<string>03.using namespace std;04. 05.char sub[10002];06. 07.int BinarySearch(char *arr,int len,char c)08.{09.int low=0,high=len-1;10.while(low<=high)11.{12.int mid=(low+high)>>1;13.if(c==arr[mid])14.return mid;15.else if(c>arr[mid]&&c<arr[mid+1])16.return mid+1;17.else if(c<arr[mid])18.high=mid-1;19.else20.low=mid+1;21.}22.return -1;23.}24. 25.int main()26.{27.int t;28.cin>>t;29.while(t--)30.{31.string
str;32.cin>>str;33.sub[0]=str[0];34.int size=1,len=str.size();35.for(int i=1;i<len;i++)36.{37.if(str[i]>sub[size-1])38.sub[size++]=str[i];39.else40.{41.int k=BinarySearch(sub,size,str[i]);42.if(k==-1)43.sub[0]=str[i];44.else45.sub[k]=str[i];46.}47.}48.cout<<size<<endl;49.}50.return 0;51.}
关于第二种方法，有几点要注意的地方，一开始没注意，所以错了好多次。
1，如13行所示，要考虑等于的情况。
2，如42行所示，要考虑当前读到的元素比栈中所有元素都小的情况。
参考：
http://www.cnblogs.com/liyongmou/archive/2010/07/11/1775341.html对两种方法讲解得很清楚