Lintcode 43. Maximum Subarray III

题目

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, return 8

思路

这道题是找k个none-overlapping的subarray里的maximum sum。对于这种找k个问题，基本上就是DP才能解决的问题，贪心法基本上都是错的。这里因为有两个维度，所以我们对于状态的定义也要做出调整：global[i][j] 表示前i 个数里面，组成j个subarray所能取得的max sum。local[i][j]表示前i个数里，包含第i个数组成j个subarray所能取得的max sum。

然后我们就要考虑如何写出状态转移方程。对于local，当前数要么和之前的数组相连，要么自立门户，对应到状态转移方程就是local[i][j] = Math.max(local[i-1][j] + cur, global[i-1][j-1] + cur); global[i][j] = Math.max(global[i-1][j], local[i][j]);

复杂度

time O(nk), space O(nk)

代码

  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
        // check edge case
        if (nums == null || nums.length == 0 || k <= 0) {
            return 0;
        }
        // preprocess
        // dp def
        int n = nums.length;
        int[][] global = new int[n + 1][k + 1];
        int[][] local = new int[n + 1][k + 1];
        // dp init
        Arrays.fill(global[0], Integer.MIN_VALUE/2);
        Arrays.fill(local[0], Integer.MIN_VALUE/2);

        global[0][0] = local[0][0] = 0;
        // dp iteration
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                int cur = nums[i-1];
                local[i][j] = Math.max(local[i-1][j] + cur, global[i-1][j-1] + cur);
                global[i][j] = Math.max(global[i-1][j], local[i][j]);
            }
        }
        return global[n][k];
    }
}