Simple Java DP solution O(n^2)


  • 0
    J

    For each element dp[i], it denotes the maximum length of palindrome starts from at least i + 1. If we find two identical characters arr[i], arr[j] (i < j), we can use dp[i] + 2 to update the maximum length of palindrome.

    public int longestPalindromeSubseq(String s) {
            if(s == null || s.length() == 0) return 0; 
            char[] arr = s.toCharArray();
            int maxBehindZero = 1;
            int[] dp = new int[s.length()]; // dp[i] means maximum length of palindrome behind i, doesn't contain i;
            int maxVal = 0, num = 0;
            for(int i = 1; i < arr.length; ++i){
                maxVal = 1;
                for(int j = i - 1; j >= 0; --j){
                    if(arr[j] == arr[i]){
                        num = dp[j];
                        dp[j] = Math.max(dp[j], maxVal);
                        maxVal = Math.max(maxVal, num + 2);
                    }else{
                        dp[j] = Math.max(dp[j], maxVal);
                    }
                }
                 maxBehindZero = Math.max(maxBehindZero, maxVal);
            }
            return maxBehindZero;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.