⚡Flashcard Drill➔
NeetCode #705LC-689Hard1-D Dynamic Programming
← Back to All Problems

#705 · #689 · Maximum Sum of 3 Non-Overlapping Subarrays(三个无重叠子数组的最大和)

📌 Problem Statement & Constraints

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with the maximum total sum and return their starting indices in increasing order (the lexicographically smallest if several exist). Constraints: 1 <= nums.length <= 2 * 10^4, 1 <= nums[i] < 2^16, 1 <= k <= nums.length.

💡 Core Algorithmic Approaches

  1. Precompute sums[i], the sum of the window nums[i..i+k-1], for i in 0..n-k.
  2. left[i] is the start of the best window whose start is at most i; right[i] is the best window whose start is at least i.
  3. For a middle window at i, the total is sums[left[i-k]] + sums[i] + sums[right[i+k]].
  4. Building left with a strict > and right with a >= comparison keeps the lexicographically smallest indices.

💻 Benchmark Python3 Implementation

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        m = n - k + 1                  # number of windows
        sums = [0] * m
        window = sum(nums[:k])
        sums[0] = window
        for i in range(1, m):
            window += nums[i + k - 1] - nums[i - 1]
            sums[i] = window
        left = [0] * m
        best = 0
        for i in range(m):
            if sums[i] > sums[best]:   # strict -> keep the earliest best
                best = i
            left[i] = best
        right = [0] * m
        best = m - 1
        for i in range(m - 1, -1, -1):
            if sums[i] >= sums[best]:  # prefer the earlier index on ties
                best = i
            right[i] = best
        res = []
        best_total = -1
        for i in range(k, m - k):
            l, r = left[i - k], right[i + k]
            total = sums[l] + sums[i] + sums[r]
            if total > best_total:
                best_total = total
                res = [l, i, r]
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): three linear passes over the window sums.
💾 Space Complexity
O(n): the sums, left, and right arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Using >= on left and > on right: the tie-breaking directions are opposite; getting them backwards yields a lexicographically larger answer.
  • Looping the middle window over the wrong range: it needs k <= i <= m - 1 - k so that both neighbours exist.
  • Recomputing window sums with slicing: the rolling update is O(1) per window.
  • Setting m = n: the number of windows is n - k + 1, and using n causes index errors.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems