# Max Sum 2 Subarray

``````给出数组[1, 3, -1, 2, -1, 2]，这两个子数组分别为[1, 3]和[2, -1, 2]或者[1, 3, -1, 2]和[2]，它们的最大和都是7
``````

``````子数组最少包含一个数
``````

``````要求时间复杂度为O(n)
``````

## Solution

• localMax[i] = max(localMax[i - 1] + A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);

• localMax[i] = max(localMax[i + 1] + A[i], A[i]);

## Code

``````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) {
if (nums == null)
return 0;
int len = nums.size(), currSum = 0;
int[] left = new int[len];
for (int i = 0; i < len - 1; i++) {
int sum = currSum + nums.get(i);
if (i == 0)
left[i + 1] = sum;
else
left[i + 1] = sum > left[i]? sum: left[i];
currSum = sum <= 0? 0: sum;
}
currSum = 0;
int max = Integer.MIN_VALUE;
for (int i = len - 1; i > 0; i--) {
int sum = currSum + nums.get(i);
if (sum + left[i] > max)
max = sum + left[i];
currSum = sum <= 0? 0: sum;
}
return max;
}
}
``````