NYOJ17,单调递增最长子序列

单调递增最长子序列

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 4 描写叙述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf。长度为4 输入 第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行，每行有一个字符串，该字符串的长度不会超过10000 输出 输出字符串的最长递增子序列的长度 例子输入 3 aaa ababc abklmncdefg 例子输出 1 3 7 来源 经典题目

也是到经典的DP题，还有一种思路是，就a—z的一个字符串和该字符串的最长公共子序列，想想也是对的

import java.util.Arrays; import java.util.Scanner; public class NYOJ17 { public static void main(String[] args) { Scanner cin=new Scanner(System.in); int t=cin.nextInt(); while (t-->0){ char []s=cin.next().toCharArray(); int []f=new int[s.length+5]; Arrays.fill(f, 1);//初始化为1,刚開始写成0出错了 for (int i=2;i<=s.length;i++){ //int max=Integer.MIN_VALUE; for (int j=1;j<=i-1;j++){ if (s[i-1]>s[j-1] && f[i]<f[j]+1){ f[i]=f[j]+1; } } } int max=Integer.MIN_VALUE; for (int i=1;i<=s.length;i++){ if (max<f[i]) max=f[i]; } System.out.println(max); } } }

转载于:https://www.cnblogs.com/bhlsheji/p/5314456.html

相关资源：数据结构—成绩单生成器