题解 | #最长回文子串#

import java.util.*;

public class Main {
    public static void main(String...args) {
        Scanner in = new Scanner(System.in);

        String a = in.nextLine();
        System.out.println(num(a));

        in.close();
    }
    public static int num(String input) {
        int l = input.length();
        int[][] arr = new int[l][l];
        char[] ch = input.toCharArray();
        for(int i = 0; i < l; i++)
            for(int j = i; j < l; j++) {
                if(ch[i] == ch[j])
                    arr[i][j] = 1;
                else arr[i][j] = 0;
            }
        //对上三角进行标记是否相同, 回文字符串必定会有 / 这个方向斜线的连贯
        int max = 0;
        int count = 0;

        for(int i = 0; i < l-1; i++) {
            int j = i;
            int n = 1;
            count = 0;
            while( j >= 0 && j+n <= l-1 && arr[j][j+n] == 1 ) {
                count = count + 2;
                j--;
                n = n + 2;
            }
            max = Math.max(max, count);
        }

        // 上循环是针对偶数对称, 下循环是针对奇数对称

        for(int i = 0; i < l-2; i++) {
            int j = i;
            int n = 2;
            count = 1;
            while( j >= 0 && j+n <= l-1 && arr[j][j+n] == 1 ) {
                count = count + 2;
                j--;
                n = n + 2;
            }
            max = Math.max(max, count);
        }
        return max;
    }
}

我这个解法应该O(n)了, 直接建立类似LCS的表格进行求解