# Maximum Subarray II

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

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.

## Code - Java

public class Solution {
/**
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public static int maxTwoSubArrays(ArrayList<Integer> nums) {
int len = nums.size();

int[] maxLeft = new int[len];
int[] maxRight = new int[len];

for (int i = 0; i < len; i++) {
maxLeft[i] = maxRight[i] = Integer.MIN_VALUE;
}

int sum = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
sum += nums.get(i);
max = Math.max(max, sum);
sum = sum < 0 ? 0 : sum;
maxLeft[i] = max;
}

sum = 0;
max = Integer.MIN_VALUE;
for (int i = len - 1; i >= 0; i--) {
sum += nums.get(i);
max = Math.max(max, sum);
sum = sum < 0 ? 0 : sum;
maxRight[i] = max;
}

int result = Integer.MIN_VALUE;
for (int i = 0; i < len - 1; i++) {
result = Math.max(result, maxLeft[i] + maxRight[i + 1]);
}
return result;
}
}