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

Have you met this question in a real interview? Yes
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.

解题思路：
基本解题思路是，这个题目可以看做是Maximum Subarray的一道follow up问题，Maximum Subarray是问在一侧中的一个最大的子串，这个题目是要求两个不相邻的子串之和最大，因此使用两个prefixsum，一个从左到右算最大的数据，一个从有道做计算最大的数据，然后将两个数据进行相加，求出最大的不相邻的加和。
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() == 0) {
            return 0;
        }
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = 0;
        int[] left = new int[nums.size()];
        int[] right = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            sum += nums.get(i);
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
            left[i] = max;
        }
        sum = 0; min = 0; max = Integer.MIN_VALUE;
        for (int i = nums.size() - 1; i >= 0; i--) {
            sum += nums.get(i);
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
            right[i] = max;
        }
        sum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size() - 1; i++) {
            sum = Math.max(sum, left[i] + right[i + 1]);
        }
        return sum;


    }
}

python

class Solution:
    """
    @param: nums: A list of integers
    @return: An integer denotes the sum of max two non-overlapping subarrays
    """
    def maxTwoSubArrays(self, nums):
        # write your code here
        if nums is None or len(nums) == 0:
            return 0
        left, right = [0] * len(nums), [0] * len(nums)
        summary, maxVal, minVal = 0, float('-inf'), 0
        for i in range(len(nums)):
            summary += nums[i]
            maxVal = max(maxVal, summary - minVal)
            minVal = min(summary, minVal)
            left[i] = maxVal
        summary, maxVal, minVal = 0, float('-inf'), 0
        for i in range(len(nums) - 1, -1, -1):
            summary += nums[i]
            maxVal = max(maxVal, summary - minVal)
            minVal = min(summary, minVal)
            right[i] = maxVal
        summary = float('-inf')
        for i in range(len(nums) - 1):
            summary = max(summary, left[i] + right[i + 1])
        return summary