# 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[]`进行全局查询从而得到最终结果

> 用 local 变量更新然后返回 global 最优还不够，需要保存对于每一个子问题的 global 最优（可能并不以当前位置结尾），用于后面的左右两边全局查询

相比 Prefix Sum，个人更偏好Kadane's Algorithm，但是用 **Kadane's Algorithm** 要注意**初始化**问题（从头到尾循环，必须要以 `nums[0]` 做初始化，从 `index = 1` 开始搜；或者从尾到头循环则以`nums[n-1]`初始化，从`index = n - 2`开始）。

## Solution

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

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

```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) {
        // write your code
        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>