# 0689. Maximum Sum of 3 Non-Overlapping Subarrays

<https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays>

## Description

Given an integer array `nums` and an integer `k`, find three non-overlapping subarrays of length `k` with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (**0-indexed**). If there are multiple answers, return the lexicographically smallest one.

**Example 1:**

```
**Input:** nums = [1,2,1,2,6,7,5,1], k = 2
**Output:** [0,3,5]
**Explanation:** Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
```

**Example 2:**

```
**Input:** nums = [1,2,1,2,1,2,1,2,1], k = 2
**Output:** [0,2,4]
```

**Constraints:**

* `1 <= nums.length <= 2 * 104`
* `1 <= nums[i] < 216`
* `1 <= k <= floor(nums.length / 3)`

## ac

divide and conquer, scan twice

Similar with this but not the same: [https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108231/C%2B%2BJava-DP-with-explanation-O(n](https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108231/C%2B%2BJava-DP-with-explanation-O%28n))

```java
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        // edge cases
        if (nums == null || nums.length == 0 || nums.length < 3 * k) {
            return new int[0];
        }

        // get subarray sum
        int[] subsum = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            subsum[0] += nums[i];
        }
        for (int i = 1; i < subsum.length; i++) {
            subsum[i] = subsum[i-1] - nums[i-1] + nums[i+k-1];
        }

        // dp, left[i], right[i]
        int[] left = new int[subsum.length];  // maximum to the left
        int[] right = new int[subsum.length];  // maximun to the right

        int max = 0;
        for (int i = 0; i < left.length; i++) {
            int i2 = i - k;
            if (i2 < 0) {
                left[i] = -1;
                continue;
            }
            if (subsum[i2] > subsum[max]) max = i2;  // update max value and index
            left[i] = max;
        }

        max = subsum.length - 1;
        for (int i = subsum.length - 1; i >= 0; i--) {
            int i2 = i + k;
            if (i2 >= subsum.length) {
                right[i] = -1;
                continue;
            }
            if (subsum[i2] >= subsum[max]) max = i2;
            right[i] = max;
        }

        // get result
        long maxSum = Long.MIN_VALUE;
        int[] res = new int[3];
        for (int i = 0; i < subsum.length; i++) {
            if (left[i] == -1 || right[i] == -1) continue;
            long tmpSum = subsum[left[i]] + subsum[i] + subsum[right[i]];
            if (tmpSum > maxSum) {  // update max
                maxSum = tmpSum;
                res[0] = left[i];
                res[1] = i;
                res[2] = right[i];
            }
        }

        return res;
    }
}
```

## ac2:

Don't even understand by looking at it. Impossible to figure out in the interview.

```java
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] res = new int[3];
        // edge cases
        if (nums == null || nums.length == 0 || k <= 0 || nums.length / k < 3) return res;

        int n = nums.length;
        int xSubarrays = 3; // x means how many subarrays
        int[][] max = new int[xSubarrays+1][n+1];
        int[][] idx = new int[xSubarrays+1][n+1];
        int[] sum = new int[n+1];

        // init accumulation sum, in order to get subarray sum
        for (int i = 1; i < sum.length; i++) sum[i] = sum[i-1] + nums[i-1];

        // iterate
        for (int x = 1; x <= xSubarrays; x++) {
            for (int i = x * k; i < max[0].length; i++) {
                int tmp = max[x-1][i-k] + (sum[i] - sum[i-k]);
                if (tmp > max[x][i-1]) { // find greater sum, update info
                    max[x][i] = tmp;
                    idx[x][i] = i - k;
                } else {
                    max[x][i] = max[x][i-1];
                    idx[x][i] = idx[x][i-1];
                }
            }
        }

        // get indices
        res = new int[xSubarrays];
        res[xSubarrays-1] = idx[xSubarrays][n];
        for (int i = xSubarrays - 2; i >= 0; i--) {
            int prevIdx = res[i+1];
            res[i] = idx[i+1][prevIdx];
        }

        return res;
    }
}

/*
so hard to understand the indices, a better approach is to have an example
*/
```


---

# 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://jaywin.gitbook.io/leetcode/solutions/0689-maximum-sum-of-3-non-overlapping-subarrays.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.