Maximum Subarray II

Source

• lintcode: 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.

Note
The subarray should contain at least one number

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

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(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        int[] fromLeft = new int[nums.size()];
        int[] fromRight = new int[nums.size()];
        int global = Integer.MIN_VALUE;

        //from left to right
        int local = 0;
        for (int i = 0; i < nums.size(); i++) {
            local = Math.max(nums.get(i), nums.get(i) + local);
            global = Math.max(global, local);
            fromLeft[i] = global;
        }

        //from right to left
        local = 0;
        global = Integer.MIN_VALUE;
        for (int j = nums.size() - 1; j >= 0; j--) {
            local = Math.max(nums.get(j), nums.get(j) + local);
            global = Math.max(global, local);
            fromRight[j] = global;
        }

        //
        local = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size() - 1; i++) {
            local = Math.max(local, fromLeft[i] + fromRight[i+1]);
        }
        return local;
    }
}