## Similar Problems

Similar Problems not available

# Constrained Subsequence Sum - Leetcode Solution

LeetCode: Constrained Subsequence Sum Leetcode Solution

Difficulty: Hard

Topics: sliding-window dynamic-programming heap-priority-queue array

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.

## Constrained Subsequence Sum Solution Code

`1`