一、题目描述

​ 最大单调子序列(Maximum Monotone Subsequence )-如果一个数列中第i个元素最少也和第i - 1个元素一样大，那么该序列单调递增。求字符串的一个最大单调递增子序列。

示例：

输入：s = "subsequence" 
输出：beee

• 1
• 2

二、解题思路

1. 定义状态

​ 设dp[i]表示字符串s的前i个字符的最大单调递增子序列的长度。

2. 定义状态转移方程

当s[i] >= s[k]时，有$dp[i]=max(dp[k])+1$，其中 1 <= k < i

否则$dp[i]=0$，其中1 <= k < i 。

总结为如下方程：

d p [ i ] = { m a x ( d p [ k ] ) + 1 , s [ i ] ≥ s [ k ] 1 , s [ i ] < s [ k ] dp[i] =

此状态方程理解起来很简单。

3. 初始化

​ 显然dp[0]初始化为0。

三、代码实现

/**
 * 最大单调子序列
 *
 *  @author hh
 *  @date 2021-5-16 20:52
 */
public class MaxMonotoneSubsequence {

    /**
     * 求字符串的最大单调子序列
     *
     * @param s 字符串
     * @return 最大单调子序列组成的字符串
     */
    public String maxMonotoneSubsequence(String s){
        int[] dp = new int[s.length() + 1];
        //记录最大单调子序列的数组索引
        int[] indexes = new int[s.length() + 1];
        //初始化dp[0]为0
        dp[0] = 0;
        indexes[0] = -1;
        for(int i = 1; i <= s.length(); i++){
            int parentIndex = 0;
            for(int k = 1; k < i; k++){
                if(s.charAt(i-1) >= s.charAt(k-1) && dp[i] <= dp[k]){
                    dp[i] = dp[k];
                    parentIndex = k;
                }
            }
            indexes[i] = parentIndex;
            dp[i] += 1;
        }
        return findPath(s,indexes, this.getMaxValueIndex(dp,Arrays.stream(dp).max().getAsInt())  );
    }

    public int getMaxValueIndex(int[] dp,int maxValue){
        for(int i = dp.length - 1; i >=0; i-- ){
            if(dp[i] == maxValue){
                return i;
            }
        }
        return 0;
    }

    /**
     * 构建一条最长路径
     *
     * @param s 源字符串
     * @param indexes 索引数组
     * @param maxDepth 最长数
     * @return 子序列字符串
     */
    public String findPath(String s,int[] indexes,int maxDepth){
        LinkedList<Character> characterList = new LinkedList<>();
        while (maxDepth != 0){
            characterList.addFirst(s.charAt(maxDepth - 1));
            maxDepth = indexes[maxDepth];
        }
        return characterList.stream().map(String::valueOf).collect(Collectors.joining());
    }

    public static void main(String[] args){
        String s = "subsequence";
        MaxMonotoneSubsequence maxMonotoneSubsequence = new MaxMonotoneSubsequence();
        System.out.println(maxMonotoneSubsequence.maxMonotoneSubsequence(s));
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67

四、执行结果