Maximum Subarray III

Lintcode: 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.

Note The subarray should contain at least one number

解题思路：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 int maxSubArray(ArrayList<Integer> nums, int k) {
    if (nums == null || nums.size() < k) {
        return 0;
    }
    int store[][] = new int[nums.size()+1][k+1];

    //sub表示子数组个数
    for (int sub = 1; sub <= k; sub++) {
        //i表示数组的索引i
        for (int i = sub; i <= nums.size(); i++) {
            long maxSum = Integer.MIN_VALUE;
            long localSum = 0;
            store[i][sub] = Integer.MIN_VALUE;
            for (int j = i-1; j >= sub - 1; j--) {
                localSum = Math.max(nums.get(j), localSum + nums.get(j));
                maxSum = Math.max(maxSum, localSum);
                store[i][sub] = (int) Math.max(store[j][sub-1] + maxSum, store[i][sub]);
            }
        }
    }
    return store[nums.size()][k];
}