# Maximum Subarray II

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

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

### Challenge

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

## Analysis

Maximum Subarray II 与 Maximum Subarray I 相比，有几处难点：

1. 两个不相邻subarray之和，原有的一个local变量不足，需要额外的变量来保存subarray sum，同时要求不相邻；定义`left[]`, `right[]`两个数组分别保存从左到右和从右往左的subarray sum的结果

2. 子问题保存local最优解不够，还需要保存全局最优，因此`left[]``right[]`中存的其实是当前subarray sum的global最优；比如`left[i]` 就是`[0, ..., i]` 这个subarray的能取得的最大subarray sum，`right[i]`则表示`[n - 1, ..., i]` 能取得的最大subarray sum，这个最优解不一定包含`i`位置作为结尾。

3. 最后对`left[]``right[]`进行全局查询从而得到最终结果

## Solution

Kadane's Algorithm - O(n) space, O(n) time

``````public class Solution {
/*
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public int maxTwoSubArrays(List<Integer> nums) {
if (nums == null || nums.size() == 0) return 0;
int n = nums.size();

// left[] stores the global max subarray sum for [0, ..., i]
int[] left = new int[n];

// right[] stores the global max subarray sum for [i, ..., n - 1]
int[] right = new int[n];

// Initialize left[] array
left[0] = nums.get(0);
int prevMax = left[0];
int max = left[0];
// Loop from left to right
for (int i = 1; i < n; i++) {
prevMax = Math.max(prevMax + nums.get(i), nums.get(i));
max = Math.max(max, prevMax);
left[i] = max;
}

// Initialize right[] array
right[n - 1] = nums.get(n - 1);
prevMax = right[n - 1];
max = right[n - 1];
// Loop from right to left
for (int i = n - 2; i >= 0; i--) {
prevMax = Math.max(prevMax + nums.get(i), nums.get(i));
max = Math.max(max, prevMax);
right[i] = max;
}

// Find max sum of left and right subarrays
int result = Integer.MIN_VALUE;
for (int i = 0; i < n - 1; i++) {
result = Math.max(result, left[i] + right[i + 1]);
}

return result;
}
}``````

Prefix Sum Approach - O(n) space, O(n) time

``````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 || nums.size() == 0) return 0;

int n = nums.size();

// Maximum subarray value from left/right with n elements
int[] left = new int[n];
int[] right = new int[n];

int prefixSum = 0;
int minSum = 0;
int max = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
prefixSum += nums.get(i);
max = Math.max(max, prefixSum - minSum);
minSum = Math.min(minSum, prefixSum);
left[i] = max;
}

prefixSum = 0;
minSum = 0;
max = Integer.MIN_VALUE;
for(int i = n - 1; i >= 0; i--){
prefixSum += nums.get(i);
max = Math.max(max, prefixSum - minSum);
minSum = Math.min(minSum, prefixSum);
right[i] = max;
}

int rst = Integer.MIN_VALUE;

for(int i = 0; i < n - 1; i++){
rst = Math.max(rst, left[i] + right[i + 1]);
}

return rst;
}
}``````

## Reference

https://mnmunknown.gitbooks.io/algorithm-notes/626,_dong_tai_gui_hua_ff0c_subarray_lei.html

Last updated