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

Example 1:

Input:
[1, 3, -1, 2, -1, 2]
Output:
7
Explanation:
the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2].

Example 2:

Input:
[5,4]
Output:
9
Explanation:
the two subarrays are [5] and [4].

Challenge

Can you do it in time complexity O(n) ?

Notice

The subarray should contain at least one number

Code (Java):

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(List<Integer> nums) {
        // write your code here
        if (nums == null || nums.size() < 2) {
            return 0;
        }
        
        // left[i] means the maxsum from 0 to i
        int[] left = new int[nums.size() + 1];
        
        // right[i] means the maxsum from n - 1 to i + 1
        int[] right = new int[nums.size() + 1];
        
        int sum = 0;
        int minPreSum = 0;
        left[0] = Integer.MIN_VALUE;
        for (int i = 1; i <= nums.size(); i++) {
            sum += nums.get(i - 1);
            left[i] = Math.max(left[i - 1], sum - minPreSum);
            minPreSum = Math.min(minPreSum, sum);
        }
        
        sum = 0;
        minPreSum = 0;
        right[nums.size()] = Integer.MIN_VALUE;
        for (int i = nums.size() - 1; i >= 0; i--) {
            sum += nums.get(i);
            right[i] = Math.max(right[i + 1], sum - minPreSum);
            minPreSum = Math.min(minPreSum, sum);
        }
        
        int maxSum = Integer.MIN_VALUE;
        for (int i = 1; i < nums.size(); i++) {
            maxSum = Math.max(maxSum, left[i] + right[i]);
        }
        
        return maxSum;
    }
}