CODEWITHSUNDEEP
algorithmdynamic-programmingarrays
Yuan Vivien Wang
Yuan Vivien Wang

Reputation: 35

maximum subarray iii (from lintcode) dynamic programming solution

Can anyone walk me through this solution below? What does p mean? why its range j-1 to i? Thanks Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

according to this blog(http://www.cnblogs.com/lishiblog/p/4183917.html), the DP analysis is

DP. d[i][j] means the maximum sum we can get by selecting j subarrays from the first i elements.

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

we iterate p from i-1 to j-1, so we can record the max subarray we get at current p, this value can be used to calculate the max subarray from p-1 to i when p becomes p-1.

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];


}

}

Upvotes: 0

Views: 1031

Answers (1)

Sayalic
Sayalic

Reputation: 7650

What does p mean: just a iterator. (Chinese Algorithm Coder always like short name for variable...)

Why its range j-1 to i:

Indeed, dp analysis should be:

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

Why must p >= j-1? Because as dp[i][j] define:

d[i][j] means the maximum sum we can get by selecting j subarrays from the first i elements.

You know , we can't select j sub-array without non-overlapping from j-1 elements. That is to say, dp[i][j] make sense when i >= j.

Any question, leave a comment here.

Upvotes: 1

Related Questions