↓Skip to main content
  1. Posts/

LeetCode-1425 带限制的子序列和

·1 min·
Table of Contents

LeetCode-1425 带限制的子序列和 #

Solution 1 #

子序列问题, 并且限制为元素下标, 因此考虑以子序列结尾下标为状态限制的动态规划. 用一个维护最大值的窗口优化时间. 代码如下:

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pq = []  
        for i in range(n):
            while pq and pq[0][1] < i - k:
                heapq.heappop(pq)
            if pq:
                nums[i] += max(0, -pq[0][0]) 
            heapq.heappush(pq, (-nums[i], i))
        return max(nums)