42.Maximum Subarray II

1.Description(Medium)

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 sum7.

2.Code

这个题的思路是，因为 两个subarray 一定不重叠

所以必定存在一条分割线

分开这两个 subarrays

所以 最后的部分里：

max = Integer.MIN_VALUE;

        for(int i = 0; i < size - 1; i++){

            max = Math.max(max, left[i] + right[i + 1]);

        }

        return max;

这里是在枚举 这条分割线的位置

然后 left[] 和 right[] 里分别存的是，某个位置往左的 maximum subarray 和往右的 maximum subarray