Description

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.

Example

Given[-1,4,-2,3,-2,3],k=2, return8

Solution

差点没读懂题，The number in each subarray should be contiguous这句话其实是句废话，只是解释了一边subarray的定义，是连续的数组成的array...

在Maximum Subarray II的基础上引申，用二维动归
local[i][j]表示包含第i的数， subarray个数为j的max sum
global[i][j]表示不一定包含第i个数，subarray个数为j的max sum
local[i][j] = max(local[i-1][j], global[i-1][j-1]) + nums[i-1] global[i][j] = max(global[i-1][j], local[i][j])

考虑到长度为i的数组中不可能取出i+1个subarray，得到初始状态为local[i][i] = sum(0~i), global[i][i] = local[i][i]。因此遍历的时候j的取值从i开始，并且对每个j，将local[j-1][j]和global[j-1][j]的值设为Integer.MIN_VALUE就可以保证在普通状态方程中local[j-1][j]和global[j-1][j]不被取到，从而保证local[i][i] = sum(0~i), global[i][i] = local[i][i]

因为对i的取值没有局限性，而对j的取值要基于i（j>= i）,因此把对j的遍历放在循环的外层。

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(int[] nums, int k) {
        // write your code here
        int[][] local = new int[nums.length+1][k+1];
        int[][] global = new int[nums.length+1][k+1];
        for (int j = 1; j <= k; j++) {
            local[j-1][j] = Integer.MIN_VALUE;
            global[j-1][j] = Integer.MIN_VALUE;
            for (int i = j; i <= nums.length; i++) {
                local[i][j] = Math.max(local[i-1][j], global[i-1][j-1]) + nums[i-1];
                global[i][j] = Math.max(global[i-1][j], local[i][j]);
            }
        }

        return global[nums.length][k];
    }
}