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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/array/maximum-subarray-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.