We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Constrained Subsequence Sum

Number: 1286

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Akuna Capital

Problem Description

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of the array such that for every two consecutive integers in the subsequence, with indices i and j (i < j), the condition j - i <= k holds. A subsequence is formed by deleting some (or no) numbers from the array while keeping the order of the remaining elements.

Key Insights

  • Use dynamic programming where dp[i] represents the maximum sum of a valid subsequence ending at index i.
  • For each index i, consider taking nums[i] alone or appending it to a valid subsequence ending at an index j (where i - j <= k) that maximizes the sum.
  • To efficiently obtain the maximum dp[j] in a sliding window of the last k indices, use a monotonic (decreasing) deque.
  • The idea is to maintain the window maximum and update it as we proceed through the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (O(k) extra space for the deque, with dp array using O(n))

Solution

We solve the problem by defining a dp array where dp[i] = nums[i] + max(0, maximum dp value in the window [i-k, i-1]). The trick is to include max(0, ...) to allow starting a new subsequence when previous sums are negative.
To access the maximum dp in the window in constant time, a monotonic deque is maintained that stores indices with their dp values in decreasing order.
At each index, we:

  1. Remove elements from the front of the deque if they are out of the current window (i - index > k).
  2. Use the front of the deque (if non-empty) as the maximum dp value from the previous k indices.
  3. Compute dp[i] and update the global maximum answer.
  4. Remove from the back of the deque all indices with dp values less than the current dp[i] since they are not useful.
  5. Insert the current index into the deque.

Code Solutions

# Python solution using a monotonic deque for efficient window maximum computation.
from collections import deque

def constrained_subsequence_sum(nums, k):
    n = len(nums)
    dp = [0] * n           # dp[i] stores the maximum subsequence sum ending at index i
    dp[0] = nums[0]
    result = dp[0]
    
    # Deque to store indices in a decreasing order of dp values
    deq = deque([0])
    
    for i in range(1, n):
        # Remove indices from the front which are out of the window
        while deq and i - deq[0] > k:
            deq.popleft()
        
        # The maximum dp in the window is at the front of the deque
        max_in_window = dp[deq[0]] if dp[deq[0]] > 0 else 0
        
        # Calculate dp[i] by either starting a new subsequence or extending the best one from the window
        dp[i] = nums[i] + max_in_window
        
        # Update overall answer
        result = max(result, dp[i])
        
        # Maintain the deque monotonically so that dp indices are in decreasing order
        while deq and dp[i] >= dp[deq[-1]]:
            deq.pop()
        deq.append(i)
    
    return result

# Example usage:
# print(constrained_subsequence_sum([10,2,-10,5,20], 2))
← Back to All Questions