描述
求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
- 输入
- 第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000 - 输出
- 输出字符串的最长递增子序列的长度
- 样例输入
-
3
aaa
ababc
abklmncdefg - 样例输出
-
1
3
7
有两种方式可以求解，
解法一：
首先对字符串S1进行从小到大排序，然后删除有序数组相同的字符得到S2。再求S1与S2的最长子串即可(求子串的方法见两个字符串的最长相同子序列)。
排序方法：
public static char[] sort(char[] P,ref int m)
{ for (int j = ; j < P.Length - ; j++)
{
for (int i = ; i < P.Length - - j; i++)
{
if (P[i] > P[i + ])
{
char point1 = P[i];
P[i] = P[i + ];
P[i + ] = point1;
}
}
}
char x = P[];
int k = ;
for (int i = ; i < P.Length; i++)
{
if (P[i] != x)
{
P[k] = P[i];
x = P[i];
k++;
}
}
m = k;
return P;
}
解法二：
利用动态规划的思想，求S1[0...i]的最长递增子串，只需要比较S1[0...i-1]中S1[k]与S1[i]的大小。
f(i)=max(f(i-1),f(i-2),...,f(0))+1；用一个int dp[i]数组保存当前的f(i)值，即到第i个元素的最长递增子序列。
递推方程的意思是，在求以ai为末元素的最长递增子序列时，找到所有序号在i前面且小于ai的元素aj，即j<i且aj<ai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
public static int LongestAddSubsequence(string A)
{
int longest = ;
int[] dp = new int[A.Length];
for (int i = ; i < A.Length; i++)
dp[i] = ;//初始话均为1
for (int i = ; i < A.Length; i++)
for (int j = i - ; j >= ; j--)
if (A[i] > A[j] && dp[i] < dp[j] + )//遇到比当前值小，并且长度比当前长度大的就更新当前长度
dp[i] = dp[j] + ;
for (int i = ; i < A.Length; i++)
if (dp[i] > longest)
longest = dp[i];
return longest;
}