Lintcode 42. Maximum Subarray II

题目

Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.

Example For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

思路

这道题需要找两个none-overlapping的subarray maximum sum。思路就是枚举分割线，然后在分割线的左右两边分别找max1和max2，最后global = max(max1 + max2)。这里我们需要两个辅助数组去记录区间内的maximum subarray sum。

复杂度

time O(n), space O(n)

代码

  public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        // check edge case
        if (nums == null || nums.size() == 0) {
            return Integer.MIN_VALUE;
        }
        // pre-process
        int len = nums.size();
        int[] localMax = new int[len];
        int[] leftGlobalMax = new int[len];
        localMax[0] = leftGlobalMax[0] = nums.get(0);
        for (int i = 1; i < len; i++) {
            int cur = nums.get(i);
            localMax[i] = Math.max(localMax[i - 1] + cur, cur);
            leftGlobalMax[i] = Math.max(leftGlobalMax[i - 1], localMax[i]);
        }
        localMax = new int[len];
        int[] rightGlobalMax = new int[len];
        localMax[len - 1] = rightGlobalMax[len - 1] = nums.get(len - 1);
        for (int i = len - 2; i >= 0; i--) {
            int cur = nums.get(i);
            localMax[i] = Math.max(localMax[i + 1] + cur, cur);
            rightGlobalMax[i] = Math.max(rightGlobalMax[i + 1], localMax[i]);
        }
        // main loop
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len - 1; i++) {
            int curSum = leftGlobalMax[i] + rightGlobalMax[i + 1];
            max = Math.max(max, curSum);
        }
        return max;
    }
}