⚡Flashcard Drill➔
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

  1. Let dp[i] be the best sum of a subsequence ending at index i: dp[i] = nums[i] + max(0, max(dp[j]) for j in [i-k, i-1]).
  2. The window maximum over the previous k DP values is maintained with a monotonic deque holding decreasing values.
  3. Expire indices that fall outside the window, and pop from the back any value not exceeding the current dp[i].
  4. The answer is the maximum dp value.

💻 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]] > 0 guard: a negative predecessor is worse than starting fresh.
  • Expiring with dq[0] <= i - k: the window is [i-k, i-1], so the condition is dq[0] < i - k.
  • Returning dp[-1]: the best subsequence may end anywhere, so the maximum over all dp is needed.
⚡
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 Heap / Priority Queue Problems