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.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2 Output: 37 Explanation: The subsequence is [10, 2, 5, 20]. Example 2:

Input: nums = [-1,-2,-3], k = 1 Output: -1 Explanation: The subsequence must be non-empty, so we choose the largest number. Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2 Output: 23 Explanation: The subsequence is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104

Solution

My intution is to use dynamic programming to solve this problem, since most optimal (maximum or minimum) problem can be solved this way. Let dp[i] be the maximum constrained subsequence sum ending at nums[i] which satisfying the constraint. Then

dp[i] = max(dp[i - 1], ..., dp[i - k]) + nums[i]

ret = max(dp[i])

So a straightforward implementation is below.

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        '''
        let dp[i] be the maximum subset sum with nums[i] as the last element in the subsequence
        then ret = max(dp[i]) for i in range(0,n)
        
        dp[i] = max(dp[i - 1], dp[i - 2], .., dp[i - k]) + nums[i]
        '''
        n = len(nums)
        dp = [0 for i in range(n)]
        dp[0] = nums[0]
        for i in range(1, n):
            for j in range(1, k + 1):
                dp[i] = max(dp[i], dp[i - j])
            dp[i] += nums[i]
        return max(dp)

The time complexity is O(n*k)

However, this does not pass the OJ. Could we optimize it further? The answer is yes. If we look at the innermost loop, acutally we are computing the maximum over a sliding window of size k + 1 ([i - k, i]). It is similar to problem 239. We can utilize a decreasing queue to solve it. That is when the front of queue went outside of the windowing, we pop it out. And if the end of the queue is smaller than the current val, we pop the end of the queue before appending the current val to the queue.

Below is the implementation

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = collections.deque()
        n = len(nums)
        ret = [0 for i in range(n - k + 1)]
        for i in range(n):
            while len(queue) and i - queue[0] + 1 > k:
                queue.popleft()
            while len(queue) and nums[queue[-1]] < nums[i]:
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                ret[i - k + 1] = nums[queue[0]]
        return ret

Time complexity is O(3*n). Since element is added to and poppped out of the queue once. The last return max take O(n).