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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Constrained Subsequence Sum

Difficulty: Hard

Problem Description

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.

Key Insights

  • A subsequence is formed by deleting some elements from the array while maintaining the order of the remaining elements.
  • The constraint j - i <= k implies that we can only consider elements within a window of size k.
  • A dynamic programming approach can be utilized to keep track of the maximum sums achievable at each index, with the help of a data structure to efficiently manage the maximum sums from the previous k indices.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The problem can be efficiently solved using a dynamic programming approach combined with a deque (double-ended queue) to maintain the maximum sums of the previous k indices. The main idea is to iterate through the array and for each element, calculate the maximum sum that can be obtained by including that element based on the sums of the previous k elements. The deque helps in managing the maximum sums in an efficient manner, allowing us to quickly access the highest sum from the valid range.

Code Solutions

def constrainedSubsetSum(nums, k):
    from collections import deque
    
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    max_sum_deque = deque([0])
    
    for i in range(1, n):
        # Remove indices that are out of the allowed range
        if max_sum_deque[0] < i - k:
            max_sum_deque.popleft()
        
        # Calculate the maximum sum we can get by including nums[i]
        dp[i] = nums[i] + (dp[max_sum_deque[0]] if max_sum_deque else 0)
        
        # Maintain the deque to keep track of maximum sums
        while max_sum_deque and dp[max_sum_deque[-1]] < dp[i]:
            max_sum_deque.pop()
        
        max_sum_deque.append(i)
    
    return max(dp)
← Back to All Questions