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.

Solution:

We calculate the cumulative sums from left and right first. For the above case, we will have

leftToRight = 1,4,4,5,5,6
rightToLeft = 6,5,3,3,2,2

The leftToRight[1] is the sum of the first two elements of given array (1 and 3), and the rightToLeft[1] is the sum of the last 5 elements (3, -1, 2, -1, 2). As we can see, if we sum leftToRight[1] and rightToLeft[1], we will have the largest sum, but 3 is counted twice and we valid the non-overlapping condition. Thus, we should use the max sum of leftToRight[i] and rightToLeft[i + 1].

Code:

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) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        int n = nums.size();

        int[] maxLeft = new int[n];
        int sum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            maxLeft[i] = max;
        }
        int[] maxRight = new int[n];
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            maxRight[i] = max;
        }

        max = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            max = Math.max(max, maxLeft[i] + maxRight[i + 1]);
        }
        return max;
    }
}