Constrained Subsequence Sum - Leetcode Solution

The Constrained Subsequence Sum problem on Leetcode is as follows:

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

To solve this problem, we can use dynamic programming. We can define an array dp where dp[i] represents the maximum sum of a subsequence ending at index i. To calculate dp[i], we can consider all the elements before i that satisfy the condition j - i <= k and choose the one that gives the maximum sum. That is,

dp[i] = max(dp[j] + nums[i], nums[i]) where i - k <= j < i.

The answer to the problem will be the maximum value in the dp array.

The time complexity of this solution is O(n*k) where n is the length of the input array. However, we can optimize this solution further by using a data structure like a deque to store the indices of elements that are candidates for the maximum sum. We can maintain this deque in such a way that it only stores indices that satisfy the condition j - i <= k. This way, we can reduce the time complexity of our solution to O(n).

Here's the Python code that implements this optimized solution:

def constrainedSubsetSum(nums: List[int], k: int) -> int: n = len(nums) dp = [0]*n #dp[i] stores the maximum sum of a subsequence ending at i maxSum = nums[0] #variable to keep track of the maximum sum seen so far q = collections.deque() #deque to store indices of elements that are candidates for the maximum sum

for i in range(n):
    #if deque is not empty and the first element's index is outside the window of size k, remove it
    while q and q[0] < i-k:
        q.popleft()
    
    #if deque is not empty, the maximum sum can be obtained by adding dp[q[0]] to nums[i]
    #else, the maximum sum is simply nums[i]
    dp[i] = max(dp[q[0]], 0) + nums[i]
    
    #if the maximum sum ending at i is greater than the maximum sum seen so far, update it
    maxSum = max(maxSum, dp[i])
    
    #remove all elements from the back of the deque that are smaller than dp[i]
    while q and dp[q[-1]] < dp[i]:
        q.pop()
    
    #append the index i to the back of the deque
    q.append(i)

return maxSum

This code has a time complexity of O(n) and a space complexity of O(n+k) due to the deque. We can further optimize the space complexity to O(k) by only storing the indices that satisfy the condition j-i <= k in the deque.

1