Last updated on January 21st, 2025 at 02:19 am
Here, we see a Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Dynamic Programming
Companies
Facebook, Google
Level of Question
Hard

Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution
Table of Contents
1. 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]
2. Coding Pattern Used in Solution
The coding pattern used in all the implementations is Dynamic Programming with Sliding Window.
- Sliding Window: The code calculates the sum of subarrays of size
k
using a sliding window approach, where the sum of the current subarray is derived from the previous subarray by subtracting the first element of the previous subarray and adding the next element. - Dynamic Programming: The problem is solved by breaking it into smaller overlapping subproblems. For example, the best subarray sums for the left, middle, and right subarrays are computed and stored to avoid redundant calculations.
3. Code Implementation in Different Languages
3.1 Maximum Sum of 3 Non-Overlapping Subarrays C++
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; } };
3.2 Maximum Sum of 3 Non-Overlapping Subarrays Java
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; } }
3.3 Maximum Sum of 3 Non-Overlapping Subarrays JavaScript
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]; };
3.4 Maximum Sum of 3 Non-Overlapping Subarrays Python
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]
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(n) |
Java | O(n) | O(n) |
JavaScript | O(n * m) | O(n * m) |
Python | O(n * m) | O(n * m) |
- The C++ and Java implementations are more efficient in terms of both time and space complexity because they avoid the nested loop for
m
subarrays. - The JavaScript and Python implementations use a more generalized approach that works for any number of subarrays (
m
), but this comes at the cost of higher complexity.