Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1286. Constrained Subsequence Sum

My accepted Python solution to LeetCode problem 1286, Constrained Subsequence Sum, running in 323ms.

  • Difficulty: Hard
  • Python
  • Runtime 323ms
  • Memory 32.6MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 323ms, memory 32.6MB, accepted 2025-12-29.

python
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        from collections import deque
        
        n = len(nums)
        dp = [0] * n
        dq = deque()  # Monotonic decreasing deque storing indices
        
        for i in range(n):
            # Remove elements outside the window
            while dq and dq[0] < i - k:
                dq.popleft()
            
            # dp[i] = nums[i] + max(0, max dp[j] for j in [i-k, i-1])
            dp[i] = nums[i]
            if dq:
                dp[i] = max(dp[i], nums[i] + dp[dq[0]])
            
            # Maintain monotonic decreasing deque
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            
            if dp[i] > 0:
                dq.append(i)
        
        return max(dp)

Source