algorithm - 最大子数组iii(来自lintcode)动态规划求解

Question

谁能指导我完成下面的这个解决方案？是什么意思？为什么它的范围是 j-1 到 i？谢谢 给定一个整数数组和一个数 k，找到 k 个不重叠的子数组，它们的总和最大。

每个子数组中的数字应该是连续的。

返回最大的和。

根据这篇博文(http://www.cnblogs.com/lishiblog/p/4183917.html)，DP分析是

DP。 d[i][j]表示从前i个元素中选取j个子数组所能得到的最大和。

d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)}

我们将p从i-1迭代到j-1，这样我们就可以记录下当前p得到的最大子数组，这个值可以用来计算当p变为p-1时从p-1到i的最大子数组.

public class Solution {
/**
 * @param nums: A list of integers
 * @param k: An integer denote to find k non-overlapping subarrays
 * @return: An integer denote the sum of max k non-overlapping subarrays
 */
public int maxSubArray(ArrayList<Integer> nums, int k) {
    if (nums.size()<k) return 0;
    int len = nums.size();
    //d[i][j]: select j subarrays from the first i elements, the max sum we can get.
    int[][] d = new int[len+1][k+1];
    for (int i=0;i<=len;i++) d[i][0] = 0;        

    for (int j=1;j<=k;j++)
        for (int i=j;i<=len;i++){
            d[i][j] = Integer.MIN_VALUE;
            //Initial value of endMax and max should be taken care very very carefully.
            int endMax = 0;
            int max = Integer.MIN_VALUE;                
            for (int p=i-1;p>=j-1;p--){
                endMax = Math.max(nums.get(p), endMax+nums.get(p));
                max = Math.max(endMax,max);
                if (d[i][j]<d[p][j-1]+max)
                    d[i][j] = d[p][j-1]+max;                    
            }
        }

    return d[len][k];


}

Answer 1

p 是什么意思:只是一个迭代器。 (中国的Algorithm Coder总是喜欢给变量取个简称...)

为什么它的范围是 j-1 到 i:

确实dp分析应该是:

d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)} j-1 <= p <= i-1

为什么必须 p >= j-1？因为 dp[i][j] 定义:

d[i][j]表示从前i个元素中选取j个子数组所能得到的最大和。

你知道，我们不能从 j-1 个元素中选择 j 个不非重叠的子数组。也就是说，当 i >= j 时，dp[i][j] 才有意义。

任何问题，在这里发表评论。