题目：http://acm.nyist.net/JudgeOnline/problem.php?pid=17
描述：
求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000
输出
输出字符串的最长递增子序列的长度
样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
7
一个很经典的动态规划的题目
这里写图片描述
递推关系表达式为
这里写图片描述
根据上述描述设计如下的代码：
public class Main {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
String sn=s.nextLine();
int n=Integer.parseInt(sn);
for(int i=0;i<n;i++) {
String str=s.nextLine();
char data[]=str.toCharArray();
int[] num=new int[data.length];
int max=0;
for(int j=0;j<data.length;j++) {
num[j]=1;//长度大于0的最短的字序列为1
for(int k=0;k<j;k++) {
if(data[j]>data[k]&&num[k]+1>num[j]) {//递推
num[j]=num[k]+1;
}
}
}
for(int j=0;j<data.length;j++) {
if(num[j]>max) {
max=num[j];
}
}
System.out.println(max);
}
}
}
文章地址：http://www.haha174.top/article/details/256855
源码地址：https://github.com/haha174/daylx.git
