單調遞增最長子序列（動态規劃）

單調遞增最長子序列

時間限制：3000 ms  |  記憶體限制：65535 KB

難度：4

描述

求一個字元串的最長遞增子序列的長度

如：dabdbf最長遞增子序列就是abdf，長度為4輸入

第一行一個整數0<n<20,表示有n個字元串要處理

随後的n行，每行有一個字元串，該字元串的長度不會超過10000

輸出

輸出字元串的最長遞增子序列的長度

樣例輸入

3
aaa
ababc
abklmncdefg      

樣例輸出

1
3
7      

1 #include<stdio.h>
 2 #include<string.h>
 3 int main(){char s[10010],dp[10010],maxlen;
 4 int n;
 5     scanf("%d",&n);
 6     while(n--){
 7         memset(dp,0,sizeof(dp));
 8         scanf("%s",s);
 9         dp[0]=1;
10         maxlen=1;
11         for(int i=1;s[i];i++){dp[i]=1;
12             for(int j=0;j<i;j++){
13                 if(s[j]<s[i]){
14                     dp[i]=dp[j]+1>dp[i]?dp[j]+1:dp[i];
15                 }
16             }
17             maxlen=dp[i]>maxlen?dp[i]:maxlen;
18         }
19         printf("%d\n",maxlen);
20     }
21     return 0;
22 }//camnbdef