首页 > 试题广场 >

最大子序列

[编程题]最大子序列
  • 热度指数：4175 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
对于字符串x和y, 如果擦除x中的某些字母(有可能全擦掉或者都不擦)能够得到y,我们就称y是x的子序列。例如."ncd"是"nowcoder"的子序列,而"xt"不是。
现在对于给定的一个字符串s,请计算出字典序最大的s的子序列。

输入描述:
输入包括一行,一个字符串s,字符串s长度length(1 ≤ length ≤ 50).
s中每个字符都是小写字母


输出描述:
输出一个字符串,即字典序最大的s的子序列。
示例1

输入

test

输出

tt
算法知识视频讲解
开通博客
头像 白伟仝
发表于 2020-09-03 09:43:59
从右往左遍历，遇到小的就删： import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 jalr4ever
发表于 2019-09-24 09:38:13
题目 对于字符串x和y, 如果擦除x中的某些字母(有可能全擦掉或者都不擦)能够得到y,我们就称y是x的子序列。例如."ncd"是"nowcoder"的子序列,而"xt"不是。现在对于给定的一个字符串s,请计算出字典序最大的s的子序列。 输入包括一行,一个字符串s,字符串s长度length(1 ≤ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客807522766号
发表于 2023-04-06 20:24:37
/*想获得最大字典序子序列，就要第一次挑字符串中最大字符加入答案，然后从这个字符串下一个位置开始，继续找最大的加入答案； 总结就是让答案中越靠前的字符串越大，同时又要满足答案是子序列； */ #include <bits/stdc++.h> using namespace std; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-18 17:13:46
解题思路 这道题要求找出字典序最大的子序列，关键点是： 子序列不要求连续，但要保持原有顺序 需要找出字典序最大的子序列 可以删除任意数量的字符（包括全部删除或不删除） 解题步骤： 从后向前遍历字符串 维护一个当前见过的最大字符 如果当前字符大于等于已见过的最大字符，则选择该字符 这样可以保证得 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 我怎么在飞
发表于 2024-09-18 20:46:32
s = input().strip() # 动态规划：dp[i]以i结尾的最大字典序 ''' t e/te s/ts/tes t/tt/tes/test ''' dp = ["" for _ in range(len(s))] dp[0] = s[0] for i in rang 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 未来就在眼前
发表于 2021-03-15 19:41:13
本题使用递归可以求解，每一次找出字典序最大的字母，，再从当前位置进行，再从index+1继续递归处理到字符串末尾即可 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hitzyq1
发表于 2021-09-17 15:33:19
import java.util.Arrays; import java.util.Scanner; /** * BD12 最大子序列 * @Author zhuyq * @Date 2021-09-17 */ public class Main { public static 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 DearAlice
发表于 2024-08-23 15:14:30
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new S 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-03-04 11:47:49
import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 贪心 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 2018 PHP工程师 百度 Java工程师
上传者：小小
难度：
36条回答 11231浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号