- 【描述】
-
求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
- 【输入】
-
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000 - 【输出】
- 输出字符串的最长递增子序列的长度
方法一：
=================================
=========
用一个数组保存以当前字符作为结束的最长字串
对于一个字符串 s ，申请同样长度的数组 X，X[i] 表示以s[i]结束的最长单调递增子串
X[i] = max{ X[j]+1 } ,其中0≤j<i,且s[j]<s[i]
则s的最长升序子串为 max{ X[i] }
复杂度O(N^2)
#include<iostream>
#include<string>
using namespace std;
int main(){
int N;
cin >> N;
string s;
while(N--){
cin >> s;
int* x = new int[s.length()];
for (unsigned int i=0;i<s.length();i++)
x[i] = 1;
int max = 1;
for(unsigned int i=1;i<s.length();i++){
for(int j=i-1;j>=0;j--) {
if(s[j]<s[i]){
if(x[j]+1>x[i]){
x[i] = x[j]+1;
}
}
}
if(max<x[i]) max = x[i];
}
cout << max << endl;
}
return 0;
}
方法二：
==========================================
用一数组保存最长长度为下标的最小字符。
#include<iostream>
#include <string>
using namespace std;
int main()
{
int n ;
cin>>n;
while(n--){
string str;
int count=1;
cin>>str;
int a[200];
a[0]=-999;
for (int i=0;i<str.length();i++){
for (int j=count-1;j>=0;j--){
if((int)str[i]>a[j]){
a[j+1]=str[i];
if(j+1==count) count++;
break;
}
}
}
cout<<count-1<<endl;
}
return 0;
}
方法三：
=======================================================
如果字符的范围有限,那么可以有O(N)时间的算法。
设串的字符集为S，包含N个元素，每个元素为Ak，Ai < Aj (0 <= i < j < N)。
设串T中以Ap结尾的单调递增子序列长度为len(T, Ap)，则T的单调递增子序列长度为Maxlen(T) = max(len(T,A0), len(T, A1), ..., len(T,An-1))。
如果给串T的末尾再添加一个字符Aq，则len(T + Aq, Aq) = len(T, Aq - 1) + 1。
#include<stdio.h>
int length(char * s)
{
int len[128] = {0}, i, t;
for(; *s != '\0' ; s++){
t = len[*s - 1] + 1;
for(i = *s; i < 128 && len[i] < t; i++)
len[i] = t;
}
return len[127];
}
int main()
{
int n;
char s[10001];
for(scanf("%d\n", &n); n--;)
printf("%d\n", length(gets(s)));
return 0;
}
