Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution

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

Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution

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 ComplexitySpace Complexity
C++O(n)O(n)
JavaO(n)O(n)
JavaScriptO(n * m)O(n * m)
PythonO(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.
Scroll to Top