Maximum Subarray III 43

Question

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.

Notice

The subarray should contain at least one number

Example

Given [-1,4,-2,3,-2,3], k=2, return 8

Solution

local[i][k]表示前i个元素取k个子数组并且必须包含第i个元素的最大和。

global[i][k]表示前i个元素取k个子数组不一定包含第i个元素的最大和。

local[i][k]的状态函数:

max(global[i-1][k-1], local[i-1][k]) + nums[i-1]

有两种情况,第一种是第i个元素自己组成一个子数组,则要在前i-1个元素中找k-1个子数组,第二种情况是第i个元素属于前一个元素的子数组,因此要在i-1个元素中找k个子数组(并且必须包含第i-1个元素,这样第i个元素才能合并到最后一个子数组中),取两种情况里面大的那个。

global[i][k]的状态函数:

max(global[i-1][k],local[i][k])

有两种情况,第一种是不包含第i个元素,所以要在前i-1个元素中找k个子数组,第二种情况为包含第i个元素,在i个元素中找k个子数组且必须包含第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(int[] nums, int k) {
        // write your code here
        if(nums.length < k){
            return 0;
        }

        int len = nums.length;

        //local[i][k]表示前i个元素取k个子数组并且必须包含第i个元素的最大和。
        int[][] localMax = new int[len + 1][k + 1];
        //global[i][k]表示前i个元素取k个子数组不一定包含第i个元素的最大和。
        int[][] globalMax = new int[len + 1][k + 1];

        for(int j = 1; j <= k; j++){
        //前j-1个元素不可能找到不重叠的j个子数组,因此初始化为最小值,以防后面被取到
            localMax[j - 1][j] = Integer.MIN_VALUE;
            for(int i = j; i <= len; i++){
                localMax[i][j] = Math.max(globalMax[i - 1][j - 1], localMax[i - 1][j]) + nums[i - 1];
                if(i == j){
                    globalMax[i][j] = localMax[i][j];
                }else{
                    globalMax[i][j] = Math.max(globalMax[i - 1][j], localMax[i][j]);
                }
            }
        }

        return globalMax[len][k];
    }
}

results matching ""

    No results matching ""