获取最长回文子序列的长度

Question

这个解决方案可以运行，但我不确定是否还可以改进。请问有人有什么想法吗？

class Ideone
{
    public static void main(String[] args) {    
        int arr[] = new int[] {4,1,2,3,4,5,6,5,4,3,4,4,4,4,4,4,4};  
        System.out.println(maxLengthPalindrome(arr, 0, arr.length-1));
    }

    public static int maxLengthPalindrome(int[] values, int i, int j) {
        if(j<=i) 
            return j-i+1;
        if(values[i]==values[j]) 
            return 2 + maxLengthPalindrome(values, i+1, j-1);
        else 
            return Math.max(maxLengthPalindrome(values, i+1, j), maxLengthPalindrome(values, i, j-1));      
    }
}

- John Roberts

---

如果您的解决方案有效，并且正在寻求代码改进，请前往http://codereview.stackexchange.com/。 - Luiggi Mendoza

这个问题似乎不适合在这里讨论，因为它涉及代码改进并应该发布在 http://codereview.stackexchange.com/ 上。 - Luiggi Mendoza

@LuiggiMendoza：OP并不是在寻求改进这段代码，而是在寻求对这个解决方案进行改进。我认为这完全符合本站的主题。 （如果有人发布了一个要求更好的排序算法的帖子，并且你看到他们已经成功实现了冒泡排序，你会把他们发送到codereview.stackexchange.com去学习归并排序吗？） - ruakh

没有明确问题陈述的问题对其他读者没有用处，因此我投票支持保持关闭状态。代码有什么问题？哪些部分不起作用？为什么您认为需要改进它？ - Mike

最长子字符串问题通常是 O(N^2)。当然，你可以使用动态规划、滚动哈希或 A* 的一维版本来优化典型的运行时间。优化的选择基于典型数据。 - Dima Tisnek

Answer 1

你的方法存在问题，即会导致对完全相同的子数组进行多次重复调用。请考虑以下序列：

1 2 3 4 5

您将对这两个子数组进行递归调用：

2 3 4 5
1 2 3 4

这又涉及到对以下内容进行递归调用：

3 4 5
2 3 4
2 3 4      // duplicate!
1 2 3

这反过来涉及到：

4 5
3 4
3 4        // duplicate!
2 3
3 4        // duplicate!
2 3        // duplicate!
2 3        // duplicate!
1 2

你看到问题了。因此，算法的总复杂度是指数级的O(2ⁿ)，即使总调用次数只有二次方级别的O(n²)。

更好的方法是使用称为动态规划（或“自底向上递归”）的技术：可以使用一个n×n数组来跟踪每个子阵列中最长回文子序列的长度。从“底部”开始——将长度为1的每个子阵列中最长回文子序列的长度存储起来，然后继续处理长度为2的子阵列，以此类推。在每次遍历中，您都可以使用所有先前遍历的结果。只有一个长度为n的子阵列，您想要的答案就是它的最长回文子序列的长度。

请注意，对于每个步骤（例如长度为m的子数组），实际上只需要前两个步骤（长度分别为m-1和m-2的子数组），因此可以通过使用两个长度为n的一维数组而不是一个大小为n×n的二维数组来优化空间；但是，在你用n×n的数组使它能够工作之后，我建议你再进行这种优化（因为将所有先前的结果打印成矩阵的能力可能有助于调试）。

- ruakh