NYOJ17,单调递增最长子序列
2024-10-19 16:45:19
单调递增最长子序列
时间限制: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);
}
} }
最新文章
- Mysql的用户名密码设置方法
- 在Linux下的中断方式读取按键驱动程序
- python 多线程实例
- 微信公众平台推出";微信保护";提升微信账号安全 附微信保护开启教程
- 清理DBA_DATAPUMP_JOBS中的孤立数据泵作业
- [转] Android OkHttp完全解析 是时候来了解OkHttp了
- JS中把字符串转成JSON对象的方法
- hashmap和hashtable,arraylist和vector的区别
- Lombok - 消除冗长的 java 代码
- 常用mysql命令(经常更新)
- 使用atomic一定是线程安全的吗
- [转] Web性能压力测试工具之ApacheBench(ab)详解
- 浅谈Java内存及GC
- PropertyPlaceholderConfigurer类的使用注意
- (二)给IE6-IE9中的input添加HTML5新属性-placeholder
- 推荐一款接口文档在线管理系统-MinDoc
- sqlserver一些对象的创建
- 重新认识 Delphi
- 【Git】 GitLab简单使用
- FindResource () RT_HTML 为什么总是出错呢 ?