Last updated on July 20th, 2024 at 04:10 am

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

Topics

Array, Dynamic Programming

Companies

Facebook, Google

Level of Question

Hard

Maximum Sum of 3 Non-Overlapping Subarrays 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]

1. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution 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;
    }
};

2. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution 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. Maximum Sum of 3 Non-Overlapping Subarrays Solution 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];
};

4. Maximum Sum of 3 Non-Overlapping Subarrays Solution 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]