Maximum Subarray III

Description

Given an array of integers and a numberk, find knon-overlappingsubarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

The subarray should contain at least one number

Example

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

Analysis

维护一个int globalMax [ k+1 ] [ len+1 ] 的矩阵， globalMax [ i ] [ j ] 代表了前 j 个数中取 i 个 subarray 得到的最大和， 注意这里第 j 个数不一定被包括。

一个 int 类型 localMax, 每次写第 globalMax 的 第 i 行 第 j 列时用到的， 记录前 j 个数中取 i 个 subarray 得到的最大和， 但包括第 j 个数。

Solution

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
        if(nums == null || nums.length == 0) return 0;

        int n = nums.length;


        int[][] localMax = new int[n + 1][k + 1];
        int[][] globalMax = new int[n + 1][k + 1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k && j <= i; j++){
                localMax[j - 1][j] = Integer.MIN_VALUE;

                localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1])
                              + nums[i - 1];
                if(i == j) globalMax[i][j] = localMax[i][j];
                else globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
            }
        }

        return globalMax[n][k];
    }
}

Reference

https://mnmunknown.gitbooks.io/algorithm-notes/626,_dong_tai_gui_hua_ff0c_subarray_lei.html