# Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution

Here, We see Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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]

## Maximum Sum of 3 Non-Overlapping Subarrays LeetCode SolutionC++

``````class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size()-k+1;
int subArraySum[n];
subArraySum[0] = 0;
for (int i = 0; i < k; i++)
subArraySum[0] += nums[i];
for (int i = 1; i < n; i++)
subArraySum[i] = subArraySum[i-1]-nums[i-1]+nums[i+k-1];
int leftBest[n];
int best = 0;
for (int i = 0; i < n; i++){
if(subArraySum[i] > subArraySum[best])
best = i;
leftBest[i] = best;
}
int rightBest[n];
best = n-1;
for (int i = n-1; i >= 0; i--){
if(subArraySum[i] >= subArraySum[best])
best = i;
rightBest[i] = best;
}
vector<int> res = {0,k,2*k};
best = subArraySum[0] + subArraySum[k] + subArraySum[k*2];
for(int i = k; i <= (nums.size()-(2*k)); i++){
int actual = subArraySum[leftBest[i-k]] + subArraySum[i] + subArraySum[rightBest[i+k]];
if (actual > best){
best = actual;
res[0] = leftBest[i-k];
res[1] = i;
res[2] = rightBest[i+k];
}
}
return res;
}
};```Code language: PHP (php)```

## Maximum Sum of 3 Non-Overlapping Subarrays LeetCode SolutionJava

``````class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] res = new int[3];
int[] psum = new int[nums.length+1];
for(int i=1; i<psum.length; i++){
psum[i] += psum[i-1]+nums[i-1];
}
int s1 = 0, s12 = 0, s123 = 0;
int i11 = -1, i21 = -1, i22 = -1;
for(int i=0; i<=nums.length - 3*k; i++){
if(s1<psum[i+k] - psum[i]){
s1 = psum[i+k] - psum[i];
i11 = i;
}
if(s1+ psum[i+2*k] - psum[i+k] > s12){
s12 = s1 + psum[i+2*k] - psum[i+k];
i21 = i11;
i22 = i+k;
}
if(s12 + psum[i+3*k] - psum[i+2*k] > s123){
s123 = s12 + psum[i+3*k] - psum[i+2*k];
res[0] = i21;
res[1] = i22;
res[2] = i+2*k;
}
}
return res;
}
}```Code language: PHP (php)```

## Maximum Sum of 3 Non-Overlapping Subarrays SolutionJavaScript

``````var maxSumOfThreeSubarrays = function(nums, k) {
let m=3, len = nums.length-k+1;
const memo = Array(len).fill(0);
memo[0] = nums.slice(k).reduce((acc, n) => acc+n);
for(let i=1;i<nums.length-k+1;i++) {
memo[i] = memo[i-1]-nums[i-1]+nums[i+k-1];
}
const sumMemo = Array.from(Array(m+1), () => [0, []]); // [sum, indexes]
for(let i=0;i<nums.length-k*m+1;i++) {
for(let j=1;j<=m;j++) {
let l = i+(j-1)*k;
let windowSum = memo[l];
let tempSum = windowSum + sumMemo[j-1][0];
if(tempSum > sumMemo[j][0]) {
const indexes = [...sumMemo[j-1][1], l];
sumMemo[j] = [tempSum, indexes];
}
}
}
return sumMemo[m][1];
};```Code language: JavaScript (javascript)```

## Maximum Sum of 3 Non-Overlapping Subarrays SolutionPython

``````class Solution:
def makeS(self,nums,k):
s = sum(nums[:k])
S = [ s ]
for i in range(k,len(nums)):
s += nums[i] - nums[i-k]
S.append( s )
return S
def maxSumOfThreeSubarrays(self, nums, k, m = 3):
L = len(nums)
if (k*m)>=L:
return sum( nums )
S    = self.makeS(nums,k)
Aprev = [ [0,[]] for _ in range(L) ]
for i in range(m):
Anew  = [ [ Aprev[0][0]+S[i*k], Aprev[0][1] + [i*k] ] ]
for j in range(i*k+1,len(S)):
sp,ip = Aprev[j-i*k]
s = S[j] + sp
if s>Anew[-1][0]:
Anew.append( [s, ip + [j] ] )
else:
Anew.append( Anew[-1] )
Aprev = Anew
return Anew[-1][-1]``````
Scroll to Top