Description

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.

Solution

1.找两个不相交的subarray可以转化为以某个index i为分水岭，将数组分隔成两个数组，左数组和有数组分别找sum最大的subarray。这样就转换成了跟maximum subarray相似的问题。在左数组中找max subarray等同于maximum subarray I，而在右数组中找max subarray按照maximum subarray I的思路，反向遍历即可。

2.不同于maximum subarray I的一点是，I中只要用一个变量max，在遍历过程中反复比对得出最终的结果即可，但在这一题中，因为不确定作为分水岭的index i究竟是哪一个，所以需要把所有遍历过程中得到的max值存下来
local[i]代表以第i个数结尾的所有subarray的最大sum
global[i]代表前i个数中所有subarray的最大sum
从左往右遍历时local[i] = max(local[i-1] + n[i], n[i]), global[i] = max(global[i-1], local[i])
从右往左遍历时local[i] = max(local[i+1] + n[i], n[i]), global[i] = max(global[i+1], local[i])

3.得到globalLeft和globalRight后，在重新遍历一边数组，确定作为左右分割点的index i即可,max = max(max, globalLeft[i] + globalLeft[i+1])

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) {
        // write your code
        int[] localLeft = new int[nums.size()];
        int[] globalLeft = new int[nums.size()];
        localLeft[0] = nums.get(0);
        globalLeft[0] = nums.get(0);
        for (int i = 1; i < nums.size(); i++) {
            localLeft[i] = Math.max(localLeft[i-1] + nums.get(i), nums.get(i));
            globalLeft[i] = Math.max(globalLeft[i-1], localLeft[i]);
        }

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

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size()-1; i++) {
            max = Math.max(max, globalLeft[i] + globalRight[i+1]);
        }

        return max;
    }
}