题解

题目难度：中等

知识点：LCS（最长公共子序列问题），动态规划

分析：

本题实际是要找出s的最长子序列，看到这个问题就应该想到利用动态规划去解决。一般是找s1、s2两个字符串中的最长子序列，那么该题中就可以遍历s,以每个字符位置作为分割点，将s分割成s1和s2两个字符串，利用动态规划去求解s1和s2中的最长子序列，结果存储在dp[i][j]的二维数组中。对于dp数组，下标从1开始对应字符串中的0下标对应的字符。

通过上面一个dp数组表，就可以算出最长子序列长度为3

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = s.length();
        int res = 0;
        for(int i = 0; i<len; i++){
            // 遍历数组，切分字符串
            int tmp = solve(s.substring(0, i),s.substring(i));
            res = Math.max(res, tmp);
        }
        System.out.println(res*2);
    }

    // 动态规划
    private static int solve(String s1, String s2) {
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        for(int i= 1; i<s1.length()+1;i++){
            for(int j= 1; j<s2.length()+1;j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }

}