蓝桥杯刷题总结:寻找字典序最大的回文子序列

P12344 [蓝桥杯 2025 省 B/Python B 第二场] 破解信息 - 洛谷

分析

乍看题目，既要不连续子序列，又要回文串，又要字典序最大

我们的思路可能会被误导，可能会先找所有是回文串的子序列，再把所有符合要求的子序列进行字典排序，再去寻找最大的。

这样的思路非常复杂，且不容易实现。

仔细思考，字典序最大需要让原串中的最大字符作为结果串的首字符，同时为了满足回文串的要求，就需要最后一个字符也为最大字符。此时我们考虑中间部分呢，或许我们认为中间可以存放其他字符如"dcd"，但是与不存放对比，"dd"的字典序显然比"dcd"大。所以中间不存放任何字符，我们只统计最大字符有几个，结果串就存放几个，显然就是答案。

因此，简化问题，同时也简化思路。

代码

import java.util.Scanner; public class Main{ public static void main(String[]args){ Scanner sc=new Scanner(System.in); String s=sc.nextLine(); char maxChar='a'; for(int i=0;i<s.length();i++){ maxChar=(char)Math.max(maxChar,s.charAt(i)); } StringBuilder str=new StringBuilder(); for(int j=0;j<s.length();j++){ if(s.charAt(j)==maxChar){ str.append(maxChar); } } System.out.println(str); } }

注意

在循环中拼接字符串时：

String：每次拼接都会创建新对象，效率低

StringBuilder：只在同一个对象上修改，效率高

所以要用StringBuilder。