# Maximum Sum of 3 Non-Overlapping Subarrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-3-non-overlapping-subarrays
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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)`

# Approaches
## Brute Force with Pre-computation
This approach involves checking every possible combination of three non-overlapping subarrays of length `k`. To make the sum calculation for each subarray efficient, we first pre-compute the sums of all possible subarrays of length `k` and store them. Then, we use three nested loops to find the combination of three subarrays that yields the maximum total sum.
**Time:** O(n^3). Pre-computing the sums takes O(n), but the three nested loops dominate the runtime, making it cubic in the size of the input array. · **Space:** O(n) to store the pre-computed sums of all subarrays of length k.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient with a time complexity of O(n^3).; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The most straightforward way to solve this problem is to try every single valid triplet of starting indices `(i, j, l)`. A subarray of length `k` can start at any index from `0` to `n-k`. For three non-overlapping subarrays, the starting indices must satisfy `0 <= i < j < l`, `j >= i + k`, and `l >= j + k`.

To avoid re-calculating the sum of each subarray in O(k) time within the loops, we can pre-calculate these sums. We create an array, let's call it `sums`, where `sums[x]` holds the sum of elements from `nums[x]` to `nums[x+k-1]`. This `sums` array can be populated in O(n) time using a sliding window.

After pre-computation, we iterate through all possible `i`, `j`, and `l`, find their corresponding sums from the `sums` array, and check if their total sum is the maximum found so far. The first set of indices that gives the maximum sum will be the lexicographically smallest due to the ordered iteration.

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

        long[] sums = new long[n - k + 1];
        long currentSum = 0;
        for (int i = 0; i < n; i++) {
            currentSum += nums[i];
            if (i >= k) {
                currentSum -= nums[i - k];
            }
            if (i >= k - 1) {
                sums[i - k + 1] = currentSum;
            }
        }

        long maxSum = 0;
        int[] result = new int[3];

        for (int i = 0; i <= n - 3 * k; i++) {
            for (int j = i + k; j <= n - 2 * k; j++) {
                for (int l = j + k; l <= n - k; l++) {
                    long currentTotalSum = sums[i] + sums[j] + sums[l];
                    if (currentTotalSum > maxSum) {
                        maxSum = currentTotalSum;
                        result[0] = i;
                        result[1] = j;
                        result[2] = l;
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create an array `sums` where `sums[i]` stores the sum of the subarray of length `k` starting at index `i`. This is computed in O(n) time using a sliding window.
- Initialize `maxSum` to 0 and `result` to store the three indices.
- Use three nested loops to iterate through all valid combinations of starting indices `i`, `j`, and `l`.
  - The outer loop for `i` runs from `0` to `n - 3k`.
  - The middle loop for `j` runs from `i + k` to `n - 2k`.
  - The inner loop for `l` runs from `j + k` to `n - k`.
- Inside the loops, calculate the total sum `sums[i] + sums[j] + sums[l]`.
- If the current sum is greater than `maxSum`, update `maxSum` and the `result` indices.
- Because the loops iterate through indices in increasing order, the first combination found for a maximum sum will be the lexicographically smallest.

## Dynamic Programming with O(n^2) Complexity
This approach improves upon the brute-force method by reducing one level of loop nesting. We still iterate through possible starting positions for the first two subarrays, `i` and `j`. However, instead of a third loop for the third subarray, we pre-compute the best possible third subarray for any given starting point. This optimization reduces the time complexity from cubic to quadratic.
**Time:** O(n^2). The pre-computation steps take O(n) time, but the two nested loops for indices `i` and `j` result in a quadratic time complexity. · **Space:** O(n) for storing the `sums` and `rightMax` arrays.
**Pros:** Significantly more efficient than the O(n^3) brute-force approach.; Builds a good foundation for the fully optimal O(n) solution.
**Cons:** While better than brute force, it may still be too slow and time out for the largest possible inputs under the given constraints.
### Explanation
We can optimize the O(n^3) solution by removing the innermost loop. The goal of the innermost loop for a fixed `i` and `j` is to find an index `l >= j+k` that maximizes `sums[l]`. This search can be optimized.

We can pre-compute an array, say `rightMax`, where `rightMax[x]` stores the index of the maximum value in the suffix of the `sums` array starting at `x`. This `rightMax` array can be computed in O(n) time by iterating backwards. To handle the lexicographical requirement, if two subarrays have the same maximum sum, we choose the one with the smaller starting index.

With `sums` and `rightMax` pre-computed, we only need two nested loops for `i` and `j`. For each pair `(i, j)`, the best starting index for the third subarray, `l`, is simply `rightMax[j+k]`. This allows us to find the total sum in O(1) time inside the loops.

```java
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        long[] sums = new long[n - k + 1];
        long currentSum = 0;
        for (int i = 0; i < n; i++) {
            currentSum += nums[i];
            if (i >= k) {
                currentSum -= nums[i - k];
            }
            if (i >= k - 1) {
                sums[i - k + 1] = currentSum;
            }
        }

        int[] rightMax = new int[n - k + 1];
        rightMax[n - k] = n - k;
        for (int i = n - k - 1; i >= 0; i--) {
            if (sums[i] >= sums[rightMax[i + 1]]) {
                rightMax[i] = i;
            } else {
                rightMax[i] = rightMax[i + 1];
            }
        }

        long maxSum = 0;
        int[] result = new int[3];

        for (int i = 0; i <= n - 3 * k; i++) {
            for (int j = i + k; j <= n - 2 * k; j++) {
                int l = rightMax[j + k];
                long currentTotalSum = sums[i] + sums[j] + sums[l];
                if (currentTotalSum > maxSum) {
                    maxSum = currentTotalSum;
                    result[0] = i;
                    result[1] = j;
                    result[2] = l;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- First, compute the `sums` array of all subarray sums of length `k` in O(n) time.
- Create an auxiliary array, `rightMax`, where `rightMax[i]` stores the starting index of the subarray with the maximum sum in the range `[i, n-k]`. This is computed in O(n) by iterating from right to left.
- Initialize `maxSum` and a `result` array.
- Use two nested loops to fix the starting indices `i` and `j` of the first two subarrays.
- For each pair `(i, j)`, find the optimal third subarray's start index `l` from `rightMax[j+k]`.
- Calculate the total sum `sums[i] + sums[j] + sums[l]` and update the `maxSum` and `result` if a better combination is found.

## Optimal Dynamic Programming with O(n) Complexity
This is the most efficient approach, solving the problem in linear time using dynamic programming and pre-computation. The key insight is to iterate through all possible middle subarrays and, for each one, quickly find the best possible non-overlapping left and right subarrays. This is achieved by pre-computing the optimal choices for the left and right parts.
**Time:** O(n). Each of the four main steps (calculating `sums`, `leftMax`, `rightMax`, and the final loop) takes O(n) time, leading to a linear overall time complexity. · **Space:** O(n) to store the `sums`, `leftMax`, and `rightMax` arrays.
**Pros:** Optimal time complexity of O(n), making it very efficient for large inputs.; The logic of breaking down the problem by fixing the middle element is a powerful and reusable pattern.
**Cons:** Requires more space compared to a naive brute-force approach due to auxiliary arrays.; The logic is more complex to implement correctly compared to simpler approaches.
### Explanation
This optimal solution is based on the idea of fixing the middle subarray and finding the best left and right subarrays efficiently. Let the middle subarray start at index `j`. It can range from `k` to `n - 2k`.

For a fixed `j`, the first subarray must start at an index `i` in `[0, j-k]`, and the third subarray must start at an index `l` in `[j+k, n-k]`. To maximize the total sum `sums[i] + sums[j] + sums[l]`, we need to maximize `sums[i]` and `sums[l]` independently.

We can pre-compute the answers for these subproblems:
1.  **`leftMax` array**: `leftMax[x]` stores the index of the subarray with the maximum sum in the range `[0, x]`. This can be computed in O(n) with a single pass from left to right.
2.  **`rightMax` array**: `rightMax[x]` stores the index of the subarray with the maximum sum in the range `[x, n-k]`. This is computed in O(n) with a pass from right to left.

After computing the `sums`, `leftMax`, and `rightMax` arrays, we can iterate through each possible middle index `j`. For each `j`, the best left index is `leftMax[j-k]` and the best right index is `rightMax[j+k]`. We calculate the total sum and update our answer if it's a new maximum. This entire process takes only linear time and space.

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

        // Calculate sums of all subarrays of size k
        long[] sums = new long[n - k + 1];
        long currentSum = 0;
        for (int i = 0; i < n; i++) {
            currentSum += nums[i];
            if (i >= k) {
                currentSum -= nums[i - k];
            }
            if (i >= k - 1) {
                sums[i - k + 1] = currentSum;
            }
        }

        // Calculate leftMax: leftMax[i] is the index of the max sum in sums[0...i]
        int[] leftMax = new int[sums.length];
        int bestIndex = 0;
        for (int i = 0; i < sums.length; i++) {
            if (sums[i] > sums[bestIndex]) {
                bestIndex = i;
            }
            leftMax[i] = bestIndex;
        }

        // Calculate rightMax: rightMax[i] is the index of the max sum in sums[i...sums.length-1]
        int[] rightMax = new int[sums.length];
        bestIndex = sums.length - 1;
        for (int i = sums.length - 1; i >= 0; i--) {
            // For lexicographically smallest, if sums are equal, choose smaller index.
            if (sums[i] >= sums[bestIndex]) {
                bestIndex = i;
            }
            rightMax[i] = bestIndex;
        }

        // Iterate through middle subarray start index j
        long maxSum = 0;
        int[] result = new int[3];

        for (int j = k; j <= n - 2 * k; j++) {
            int i = leftMax[j - k];
            int l = rightMax[j + k];
            long currentTotalSum = sums[i] + sums[j] + sums[l];

            if (currentTotalSum > maxSum) {
                maxSum = currentTotalSum;
                result[0] = i;
                result[1] = j;
                result[2] = l;
            }
        }

        return result;
    }
}
```
### Algorithm
- Calculate the `sums` array using a sliding window in O(n) time.
- Create a `leftMax` array where `leftMax[i]` stores the index of the maximum sum in `sums[0...i]`. Compute this in O(n) with a left-to-right pass.
- Create a `rightMax` array where `rightMax[i]` stores the index of the maximum sum in `sums[i...n-k]`. Compute this in O(n) with a right-to-left pass, preferring smaller indices on ties for lexicographical order.
- Initialize `maxSum` and a `result` array.
- Iterate with a single loop for the middle subarray's starting index `j` from `k` to `n - 2k`.
- For each `j`, find the best left index `i = leftMax[j-k]` and the best right index `l = rightMax[j+k]` in O(1) time.
- Calculate the total sum and update `maxSum` and `result` if a new maximum is found.

# Solutions
### Java

```java
class Solution {
public
  int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int[][] pre = new int[n][0];
    int[][] suf = new int[n][0];
    for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) {
      int cur = s[i + k] - s[i];
      if (cur > t) {
        pre[i + k - 1] = new int[]{cur, i};
        t = cur;
        idx = i;
      } else {
        pre[i + k - 1] = new int[]{t, idx};
      }
    }
    for (int i = n - k, t = 0, idx = 0; i >= 0; --i) {
      int cur = s[i + k] - s[i];
      if (cur >= t) {
        suf[i] = new int[]{cur, i};
        t = cur;
        idx = i;
      } else {
        suf[i] = new int[]{t, idx};
      }
    }
    int[] ans = new int[0];
    for (int i = k, t = 0; i < n - 2 * k + 1; ++i) {
      int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0];
      if (cur > t) {
        ans = new int[]{pre[i - 1][1], i, suf[i + k][1]};
        t = cur;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> s(n + 1, 0);
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    vector<vector<int>> pre(n, vector<int>(2, 0));
    vector<vector<int>> suf(n, vector<int>(2, 0));
    for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) {
      int cur = s[i + k] - s[i];
      if (cur > t) {
        pre[i + k - 1] = {cur, i};
        t = cur;
        idx = i;
      } else {
        pre[i + k - 1] = {t, idx};
      }
    }
    for (int i = n - k, t = 0, idx = 0; i >= 0; --i) {
      int cur = s[i + k] - s[i];
      if (cur >= t) {
        suf[i] = {cur, i};
        t = cur;
        idx = i;
      } else {
        suf[i] = {t, idx};
      }
    }
    vector<int> ans;
    for (int i = k, t = 0; i < n - 2 * k + 1; ++i) {
      int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0];
      if (cur > t) {
        ans = {pre[i - 1][1], i, suf[i + k][1]};
        t = cur;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]: n = len(nums) s = list(accumulate(nums, initial=0)) pre = [[] for _ in range(n)] suf = [[] for _ in range(n)] t = idx = 0 for i in range(n - k + 1): if (cur: = s[i + k] - s[i]) > t: pre[i + k - 1] = [cur, i] t, idx = pre[i + k - 1] else: pre[i + k - 1] = [t, idx] t = idx = 0 for i in range(n - k, - 1, - 1): if (cur: = s[i + k] - s[i]) >= t: suf[i] = [cur, i] t, idx = suf[i] else: suf[i] = [t, idx] t = 0 ans = [] for i in range(k, n - 2 * k + 1): if (cur: = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]) > t: ans = [pre[i - 1][1], i, suf[i + k][1]] t = cur return ans

```