# Maximum Subarray II

## Question

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.

Note
The subarray should contain at least one number

Challenge
Can you do it in time complexity O(n) ?

## 题解

### 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(ArrayList<Integer> nums) {
// -1 is not proper for illegal input
if (nums == null || nums.isEmpty()) return -1;

int size = nums.size();
// get max sub array forward
int[] maxSubArrayF = new int[size];
forwardTraversal(nums, maxSubArrayF);
// get max sub array backward
int[] maxSubArrayB = new int[size];
backwardTraversal(nums, maxSubArrayB);
// get maximum subarray by iteration
int maxTwoSub = Integer.MIN_VALUE;
for (int i = 0; i < size - 1; i++) {
// non-overlapping
maxTwoSub = Math.max(maxTwoSub, maxSubArrayF[i] + maxSubArrayB[i + 1]);
}

return maxTwoSub;
}

private void forwardTraversal(List<Integer> nums, int[] maxSubArray) {
int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
int size = nums.size();
for (int i = 0; i < size; i++) {
minSum = Math.min(minSum, sum);
sum += nums.get(i);
maxSub = Math.max(maxSub, sum - minSum);
maxSubArray[i] = maxSub;
}
}

private void backwardTraversal(List<Integer> nums, int[] maxSubArray) {
int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
int size = nums.size();
for (int i = size - 1; i >= 0; i--) {
minSum = Math.min(minSum, sum);
sum += nums.get(i);
maxSub = Math.max(maxSub, sum - minSum);
maxSubArray[i] = maxSub;
}
}
}