NeetCode #554LC-1425HardHeap / Priority Queue
← Back to All Problems#554 · #1425 · Constrained Subsequence Sum(带限制的子序列和)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return the maximum sum of a non-empty subsequence such that for every two consecutive chosen indices i < j, j - i <= k. Constraints: 1 <= k <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4.💡 Core Algorithmic Approaches
- Let
dp[i]be the best sum of a subsequence ending at indexi:dp[i] = nums[i] + max(0, max(dp[j]) for j in [i-k, i-1]). - The window maximum over the previous
kDP values is maintained with a monotonic deque holding decreasing values. - Expire indices that fall outside the window, and pop from the back any value not exceeding the current
dp[i]. - The answer is the maximum
dpvalue.
💻 Benchmark Python3 Implementation
class Solution:
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
from collections import deque
n = len(nums)
dp = [0] * n
dq = deque() # indices with decreasing dp values
for i in range(n):
while dq and dq[0] < i - k:
dq.popleft() # outside the window
# either start fresh here, or extend the best previous choice
dp[i] = nums[i] + (dp[dq[0]] if dq and dp[dq[0]] > 0 else 0)
while dq and dp[dq[-1]] <= dp[i]:
dq.pop() # dominated by the current value
dq.append(i)
return max(dp)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index enters and leaves the deque once.
💾 Space Complexity
O(n) for the DP array and O(k) for the deque.
⚠️ Interview Pitfalls & Follow-ups
- Using
max(dp[i-k:i])directly: O(n * k); the deque gives the window maximum in O(1) amortised. - Forgetting the
dp[dq[0]] > 0guard: a negative predecessor is worse than starting fresh. - Expiring with
dq[0] <= i - k: the window is[i-k, i-1], so the condition isdq[0] < i - k. - Returning
dp[-1]: the best subsequence may end anywhere, so the maximum over alldpis needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.