Maximum Subarray II

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.

Notice: The subarray should contain at least one number

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.

Challenge: Can you do it in time complexity 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) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int[] left = new int[nums.size()];
        
        for (int i = 0; i < nums.size(); i++) {
            sum = Math.max(sum + nums.get(i), nums.get(i));
            max = Math.max(sum, max);
            left[i] = max;
        }
        
        sum = 0;
        max = Integer.MIN_VALUE;
        int result = Integer.MIN_VALUE;
        
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (i < nums.size() - 1) {
                result = Math.max(result, left[i] + max);
            }
            
            sum = Math.max(sum + nums.get(i), nums.get(i));
            max = Math.max(sum, max);
        }
        
        return result;
    }
}

Here is another solution to this problem.

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 sum = 0;
        int max = Integer.MIN_VALUE;
        int[] left = new int[nums.size()];
        
        for (int i = 0; i < nums.size(); i++) {
            sum = Math.max(sum + nums.get(i), nums.get(i));
            max = Math.max(sum, max);
            left[i] = max;
        }
        
        sum = 0;
        max = Integer.MIN_VALUE;
        int[] right = new int[nums.size()];
        for (int i = nums.size() - 1; i >= 0; i--) {
            sum = Math.max(sum + nums.get(i), nums.get(i));
            max = Math.max(sum, max);
            right[i] = max;
        }
        
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size() - 1; i++) {
            result = Math.max(result, left[i] + right[i + 1]);
        }
        
        return result;
    }
}

Hope this helps,
Michael