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
- Precompute
sums[i], the sum of the windownums[i..i+k-1], foriin0..n-k. left[i]is the start of the best window whose start is at mosti;right[i]is the best window whose start is at leasti.- For a middle window at
i, the total issums[left[i-k]] + sums[i] + sums[right[i+k]]. - Building
leftwith a strict>andrightwith 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
>=onleftand>onright: 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 - kso that both neighbours exist. - Recomputing window sums with slicing: the rolling update is O(1) per window.
- Setting
m = n: the number of windows isn - k + 1, and usingncauses index errors.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.