Maximum Sum of 3 Non-Overlapping Subarrays

Hard
1501.

Maximum Sum of 3 Non-Overlapping Subarrays

Maximum Sum of 3 Non-Overlapping Subarrays is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Meta interviews.

Given an integer array nums and an integer k, choose three non-overlapping subarrays, each of length exactly k, whose elements add up to the largest possible total.

Return the 0-indexed starting positions of the three subarrays in increasing order. When several choices reach the same maximum total, return the one whose list of positions is lexicographically smallest.

Example 1

Input
nums = [3,1,3,1,8,9,4,1], k = 2
Output
[0,3,5]
Explanation
The window sums are `[4,4,4,9,17,13,5]`. The best total is 26, reached by `[0,3,5]`, `[1,3,5]`, `[0,4,6]` and others; `[0,3,5]` is the smallest.

Example 2

Input
nums = [2,2,2,2,2,2], k = 1
Output
[0,1,2]
Explanation
Every choice totals 6, so the earliest positions win.

Example 3

Input
nums = [4,5,10,6,11,17,4,11,1,3], k = 1
Output
[4,5,7]
Explanation
The three largest single values are 11, 17 and 11.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] < 2^16
  • 1 <= k <= floor(nums.length / 3)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSumOfThreeSubarrays = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Sum of 3 Non-Overlapping Subarrays — Solution

Maximum Sum of 3 Non-Overlapping Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Sum of 3 Non-Overlapping Subarrays is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Meta interviews.

Problem statement

Given an integer array nums and an integer k, choose three non-overlapping subarrays, each of length exactly k, whose elements add up to the largest possible total.

Return the 0-indexed starting positions of the three subarrays in increasing order. When several choices reach the same maximum total, return the one whose list of positions is lexicographically smallest.

Example 1

Input: nums = [3,1,3,1,8,9,4,1], k = 2
Output: [0,3,5]
Explanation: The window sums are `[4,4,4,9,17,13,5]`. The best total is 26, reached by `[0,3,5]`, `[1,3,5]`, `[0,4,6]` and others; `[0,3,5]` is the smallest.

Example 2

Input: nums = [2,2,2,2,2,2], k = 1
Output: [0,1,2]
Explanation: Every choice totals 6, so the earliest positions win.

Example 3

Input: nums = [4,5,10,6,11,17,4,11,1,3], k = 1
Output: [4,5,7]
Explanation: The three largest single values are 11, 17 and 11.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] < 2^16
  • 1 <= k <= floor(nums.length / 3)

Hints for Maximum Sum of 3 Non-Overlapping Subarrays

  1. Hint 1

    Precompute the sum of every window of length k. Now pick three window starts a < b < c with b ≥ a + k and c ≥ b + k.

  2. Hint 2

    Fix the middle window b. The best left window is the best one starting anywhere in [0, b - k]; the best right window is the best one starting in [b + k, last].

  3. Hint 3

    Precompute the position of the best window on every prefix and on every suffix — keeping the leftmost one on ties — then scan b from left to right and replace the answer only on a strictly larger total.

How to solve Maximum Sum of 3 Non-Overlapping Subarrays

Once window sums are known, the three windows interact only through the middle one: for a fixed middle start b, the left and right choices are independent maximisations over a prefix and a suffix of the window array. Prefix and suffix argmax tables make each middle choice O(1).

Approach

  1. Compute win[i], the sum of nums[i..i+k-1], for every start i with a sliding window.
  2. left[i] = the start of a maximal window among win[0..i], keeping the earliest on ties (update only on >).
  3. right[i] = the start of a maximal window among win[i..], keeping the earliest on ties (scanning right to left, update on >=).
  4. For every middle start b from k to len(win) - 1 - k: the candidate is (left[b-k], b, right[b+k]).
  5. Keep the first candidate with the largest total, replacing it only on a strictly larger total. Return it.

Why it works

For a fixed middle window the total is win[a] + win[b] + win[c] with a ≤ b - k and c ≥ b + k, so choosing the best a and the best c independently is optimal. The tie rules give the lexicographically smallest optimum: suppose an optimal triple used a smaller a' with a later middle b'; then a' lies outside [0, b - k] for the first optimal middle b (otherwise the leftmost-argmax rule would have chosen it), which forces a' > b - k ≥ a — a contradiction. The same argument applies to b and c.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The suffix table must prefer the leftmost window on ties — update on >= while scanning right to left.
  • The outer scan must replace only on a strictly larger total, or a later middle window can displace an equally good earlier one.
  • The middle start runs from k to len(win) - 1 - k inclusive; the constraints guarantee at least one value.

Reference solution

Python

from typing import List

def maxSumOfThreeSubarrays(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    m = n - k + 1
    win = [0] * m
    s = 0
    for i in range(n):
        s += nums[i]
        if i >= k:
            s -= nums[i - k]
        if i >= k - 1:
            win[i - k + 1] = s
    left = [0] * m
    best = 0
    for i in range(m):
        if win[i] > win[best]:
            best = i
        left[i] = best
    right = [0] * m
    best = m - 1
    for i in range(m - 1, -1, -1):
        if win[i] >= win[best]:
            best = i
        right[i] = best
    ans, top = [], -1
    for b in range(k, m - k):
        a, c = left[b - k], right[b + k]
        total = win[a] + win[b] + win[c]
        if total > top:
            top = total
            ans = [a, b, c]
    return ans

Java

public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    int n = nums.length, m = n - k + 1;
    long[] win = new long[m];
    long s = 0;
    for (int i = 0; i < n; i++) {
        s += nums[i];
        if (i >= k) s -= nums[i - k];
        if (i >= k - 1) win[i - k + 1] = s;
    }
    int[] left = new int[m], right = new int[m];
    int best = 0;
    for (int i = 0; i < m; i++) {
        if (win[i] > win[best]) best = i;
        left[i] = best;
    }
    best = m - 1;
    for (int i = m - 1; i >= 0; i--) {
        if (win[i] >= win[best]) best = i;
        right[i] = best;
    }
    int[] ans = new int[3];
    long top = -1;
    for (int b = k; b + k < m; b++) {
        int a = left[b - k], c = right[b + k];
        long total = win[a] + win[b] + win[c];
        if (total > top) {
            top = total;
            ans = new int[] { a, b, c };
        }
    }
    return ans;
}

C++

vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    int n = nums.size(), m = n - k + 1;
    vector<long long> win(m);
    long long s = 0;
    for (int i = 0; i < n; i++) {
        s += nums[i];
        if (i >= k) s -= nums[i - k];
        if (i >= k - 1) win[i - k + 1] = s;
    }
    vector<int> left(m), right(m);
    int best = 0;
    for (int i = 0; i < m; i++) {
        if (win[i] > win[best]) best = i;
        left[i] = best;
    }
    best = m - 1;
    for (int i = m - 1; i >= 0; i--) {
        if (win[i] >= win[best]) best = i;
        right[i] = best;
    }
    vector<int> ans;
    long long top = -1;
    for (int b = k; b + k < m; b++) {
        int a = left[b - k], c = right[b + k];
        long long total = win[a] + win[b] + win[c];
        if (total > top) {
            top = total;
            ans = {a, b, c};
        }
    }
    return ans;
}

JavaScript

var maxSumOfThreeSubarrays = function(nums, k) {
    var n = nums.length, m = n - k + 1;
    var win = new Array(m);
    var s = 0;
    for (var i = 0; i < n; i++) {
        s += nums[i];
        if (i >= k) s -= nums[i - k];
        if (i >= k - 1) win[i - k + 1] = s;
    }
    var left = new Array(m), right = new Array(m);
    var best = 0;
    for (var i = 0; i < m; i++) {
        if (win[i] > win[best]) best = i;
        left[i] = best;
    }
    best = m - 1;
    for (var i = m - 1; i >= 0; i--) {
        if (win[i] >= win[best]) best = i;
        right[i] = best;
    }
    var ans = [], top = -1;
    for (var b = k; b + k < m; b++) {
        var a = left[b - k], c = right[b + k];
        var total = win[a] + win[b] + win[c];
        if (total > top) {
            top = total;
            ans = [a, b, c];
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming