九章算法 | Amazon面试题：最长的回文序列

给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 ​1000​.

在线评测地址：LintCode 领扣

样例1

输入： "bbbab"
输出： 4
解释：
一个可能的最长回文序列为 "bbbb"

样例2

输入： "bbbbb"
输出： 5 

算法：DP

设​dp[i][j]​表示在​s[i...j]​中最长回文序列的长度。

对于初始化区间长度

• 长度为​0​时，​dp[i][i] = 1​
• 对于 dp[i][j]，假设​s[i] != s[j]​
  • 那么在​sub(i,j)​的最大回文串中,​s[i]​与​s[j]​不会同时出现，那么​sub(i,j)​的最大回文串要么出现在​sub(i+1,j)​,要么出现在​sub(i,j-1)​，因此我们的状态转移方程就得到了​dp[i][j] = max(dp[i+1][j], dp[i][j-1])​
• 假设​s[i]==s[j]​
  • 那么直接认为这俩个匹配，会同时出现在结果中，然后加上​sub(i+1,j-1)​的最大回文串，即​dp[i][j] = dp[i+1][j-1] + 2​
• 最后的结果就在​dp[0][len_s-1]​

复杂度分析

• 时间复杂度​O(len(s)*len(s))​
  • 嵌套循环，顺着​i​减小的方向，以​j​增大的方向遍历
• 空间复杂度​O(len(s)*len(s))​
  • 二维dp的大小

public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    // 寻找左端点
    static int findFirstTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] < target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (left < n && A[left] == target){
            return left;
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        return -1;
    }
    
    // 寻找右端点
    static int findLastTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] <= target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        if (left < n && A[left] == target){
            return left;
        }
        return -1;
    }
    
    public int[] searchRange(int[] A, int target) {
        int n = A.length;
        int[] interval = {-1, -1};
        interval[0] = findFirstTargetNum(A, target, n);
        interval[1] = findLastTargetNum(A, target, n);
        return interval;
    }
}

更多题解参考：九章算法