LeetCode: Constrained Subset Sum

Posted on February 10, 2020July 26, 2020 by braindenny

Identity number which appears exactly once.

Similar Problems:

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

A subset 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 subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset 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 subset is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: dynamic programming + monotone queue

## https://code.dennyzhang.com/constrained-subset-sum
## Basic Ideas: monotone queue
##
##   For each element check whether to take it
##   If take it, find the previous element
##           For the previous element, the last k-1 elements are the candidates
##           From right to left, if one candidate is better 
##                than previous one, no need to keep the previous one
##
## Complexity: Time O(n), Space O(k)
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        queue = collections.deque()
        for i in range(len(nums)):
            if len(queue)>0:
                # add the previous section
                nums[i] += queue[0]
            # monotone queue: keep decreasing
            while len(queue) > 0 and queue[-1] < nums[i]:
                # remove previous useless values
                queue.pop()
            # store result as candidates
            if nums[i] > 0:
                queue.append(nums[i])
            # sliding window moves the left
            if i>=k and len(queue)>0 and queue[0] == nums[i-k]:
                queue.popleft()
        return max(nums)

Solution: dynamic programming + sliding window + heap + delayed deletion

## https://code.dennyzhang.com/constrained-subset-sum
## Basic Ideas: dynamic programming + sliding window + heap + delayed deletion
##
##   Each element whether to take it
##      Previous element
##
##   dp(i): 
##           take current element
##                max(dp(i-j))+nums[i] 1<=j<=k-1
##           don't take it
##
## Complexity: Time O(n*log(n)), Space O(n)
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        res = -sys.maxsize
        n = len(nums)
        dp = [0]*n
        li = []
        for i in range(n):
            dp[i] = nums[i]
            while len(li)>0:
                (v, j) = heapq.heappop(li)
                v = -v
                if i-j>k: continue
                heapq.heappush(li, (-v, j))
                dp[i] = max(dp[i], v+nums[i])
                break
            res = max(res, dp[i])
            heapq.heappush(li, (-dp[i], i))
        return res

Post Views: 0