## Algorithm

Problem Name: 689. Maximum Sum of 3 Non-Overlapping Subarrays

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
const maxSumOfThreeSubarrays = (nums, k) => {
let n = nums.length,
maxsum = 0
let sum = new Array(n + 1).fill(0),
posLeft = new Array(n).fill(0),
posRight = new Array(n).fill(0),
ans = new Array(3).fill(0)
for (let i = 0; i  <  n; i++) sum[i + 1] = sum[i] + nums[i]
for (let i = k, tot = sum[k] - sum[0]; i  <  n; i++) {
if (sum[i + 1] - sum[i + 1 - k] > tot) {
posLeft[i] = i + 1 - k
tot = sum[i + 1] - sum[i + 1 - k]
} else posLeft[i] = posLeft[i - 1]
}
posRight[n - k] = n - k
for (let i = n - k - 1, tot = sum[n] - sum[n - k]; i >= 0; i--) {
if (sum[i + k] - sum[i] >= tot) {
posRight[i] = i
tot = sum[i + k] - sum[i]
} else posRight[i] = posRight[i + 1]
}
for (let i = k; i  < = n - 2 * k; i++) {
let l = posLeft[i - 1],
r = posRight[i + k]
let tot = sum[i + k] - sum[i] + (sum[l + k] - sum[l]) + (sum[r + k] - sum[r])
if (tot > maxsum) {
maxsum = tot
ans[0] = l
ans[1] = i
ans[2] = r
}
}
return ans
}
``````
Copy The Code &

Input

cmd
nums = [1,2,1,2,6,7,5,1], k = 2

Output

cmd
[0,3,5]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
// dp[i] is the sum of subarray of in range [i , i + k)
// nextMax[i] is the maximum value in dp[i : dp.size() - 1]
// nextIdx[i] is the index of nextMax[i]
int n = nums.size(), sum = 0, maxRight = 0, idx = 0, maxSum = 0;
vector<int>res, dp(n - k + 1), nextMax(n - k + 1), nextIdx(n - k + 1);
// Using a sliding window to get the sum of subarray in range [i , i + k)
for(int i = 0; i  <  n; i++){
sum += nums[i];
if(i >= k) sum -= nums[i - k];
if(i >= k - 1) dp[i - k + 1] = sum;
}
// Starting from end of dp array to get the maximum value after current position
for(int i = dp.size() - 1; i >= 0; i--){
if(dp[i] > maxRight) maxRight = dp[i], idx = i;
nextMax[i] = maxRight;
nextIdx[i] = idx;
}
// Using two pointers i, j to find the result
// The third entry is determined by nextMax[j + k]
for(int i = 0; i <= n - 3 * k; i++)
for(int j = i + k; j  < = n - 2 * k; j++>{
sum = dp[i] + dp[j] + nextMax[j + k];
if(sum > maxSum){
maxSum = sum;
res = {i, j, nextIdx[j + k]};
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
nums = [1,2,1,2,6,7,5,1], k = 2

Output

cmd
[0,3,5]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxSumOfThreeSubarrays = (nums, k) => {
let n = nums.length,
maxsum = 0
let sum = new Array(n + 1).fill(0),
posLeft = new Array(n).fill(0),
posRight = new Array(n).fill(0),
ans = new Array(3).fill(0)
for (let i = 0; i  <  n; i++) sum[i + 1] = sum[i] + nums[i]
for (let i = k, tot = sum[k] - sum[0]; i  <  n; i++) {
if (sum[i + 1] - sum[i + 1 - k] > tot) {
posLeft[i] = i + 1 - k
tot = sum[i + 1] - sum[i + 1 - k]
} else posLeft[i] = posLeft[i - 1]
}
posRight[n - k] = n - k
for (let i = n - k - 1, tot = sum[n] - sum[n - k]; i >= 0; i--) {
if (sum[i + k] - sum[i] >= tot) {
posRight[i] = i
tot = sum[i + k] - sum[i]
} else posRight[i] = posRight[i + 1]
}
for (let i = k; i  < = n - 2 * k; i++) {
let l = posLeft[i - 1],
r = posRight[i + k]
let tot = sum[i + k] - sum[i] + (sum[l + k] - sum[l]) + (sum[r + k] - sum[r])
if (tot > maxsum) {
maxsum = tot
ans[0] = l
ans[1] = i
ans[2] = r
}
}
return ans
}
``````
Copy The Code &

Input

cmd
nums = [1,2,1,2,1,2,1,2,1], k = 2

Output

cmd
[0,2,4]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxSumOfThreeSubarrays(self, nums, k):
single, double, sm, n, cur = {}, {}, 0, len(nums), sum(nums[:k - 1])
for i in range(k - 1, n):
cur += nums[i]
single[i - k + 1] = cur
cur -= nums[i - k + 1]
cur = n - k, single[n - k]
for i in range(n - k, k * 2 - 1, -1):
if single[i] >= cur[1]:
cur = i, single[i]
double[i - k] = cur[1] + single[i - k], i - k, cur[0]
cur = double[n - 2 * k]
for i in range(n - 2 * k, k - 1, -1):
if double[i][0] >= cur[0]:
cur = double[i]
if single[i - k] + cur[0] >= sm:
sm, res = single[i - k] + cur[0], [i - k, cur[1], cur[2]]
return res
``````
Copy The Code &

Input

cmd
nums = [1,2,1,2,1,2,1,2,1], k = 2

Output

cmd
[0,2,4]