题目

对于字符串x和y, 如果擦除x中的某些字母(有可能全擦掉或者都不擦)能够得到y,我们就称y是x的子序列。例如."ncd"是"nowcoder"的子序列,而"xt"不是。
现在对于给定的一个字符串s,请计算出字典序最大的s的子序列。

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

输出一个字符串,即字典序最大的s的子序列。

输入：test
输出：tt

思路

一开始想着回溯，或者用 indexOf 去循环判断，但都失败了！参考了一下大佬写法，总而言之是有规律的：

• 总是在当前已经确定字符的后面的序列去查找
• 确定字符字典序前面的总是比后面的大

那么，如果是从后往前看，就是总是找比当前字符字典序大于或者相等的字符，因为后面的字符有两种情况：

• 字典序比前面的字符大
• 字典序比前面的字符小或者相等

那么，如果一开始就从后往前去比较，就能保证确定字符总是合法的，同时发现，字符串最后一个字符总是能插入的。因为开头就要最大字典序的字符开头，最后一个字符字典序要么比前面都大或等于，要么比前面的小，都可以插入

所以，最后从后往前遍历原字符序列，使用双指针，去判断字符是否可以插入即可

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        StringBuilder sb = new StringBuilder();
        int p1 = arr.length - 1;//指向原字符序列待判断字符
        int p2 = p1; 
        while (p1 >= 0 && p2 >= 0) {
            if (arr[p1] >= arr[p2]) {
                sb.append(arr[p1]);
                p2 = p1;//如果确定了，那么下一次要比较的是上一个确定下来的字符
            }
            p1--;
        }
        System.out.println(sb.reverse().toString());
    }
}

总结

代码功底不好。。。不然回溯应该也可实现，下次继续挑战