Problem

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.

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.

思路

• 与maximum subarray 做法一样,
• 由于要取两个subarray, 并且没有重合的地方. 所以将数组划分两个区间.
• [0, i] 和 [i, len - 1]
• left[i] 代表 0 ~ i 这个区间的最大子数组和, 所以一个for循环从左往右扫
• right[i] 代表 i ~ len-1 这个区间的最大子数组和, 所以另一个for循环从右往左扫
• 

    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }

        int size = nums.size();
        int[] left = new int[size];
        int[] right = new int[size];

        int min = 0;
        int sum = nums.get(0);
        left[0] = nums.get(0);
        for (int i = 1; i < size; i++) {
            min = Math.min(min, sum);
            sum += nums.get(i);
            left[i] = Math.max(left[i - 1], sum - min);
        }

        min = 0;
        sum = nums.get(size - 1);
        right[size - 1] = nums.get(size - 1); 
        for (int i = size - 2; i >= 0; i--) {
            min = Math.min(min, sum);
            sum += nums.get(i);
            right[i] = Math.max(right[i + 1], sum - min);
        }


        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < size - 1; i++) {
            ans = Math.max(ans, left[i] + right[i + 1]);
        }

        return ans;
    }