1425. 带限制的子序列和

题目描述

数组值可以是负，需要返回一个非空的子序列和的最大值。其中对子序列的要求是相邻两个元素的原始下标不能超过k

基本分析

1.怎么联想到dp？对某个i来说，不考虑之前的，那么就是num[i], 考虑之前的就是需要在i-k到i-1之间找一个最大的f[j]值，f[i] = f[j] + nums[i]
2.如果简单枚举j会有啥问题，怎么优化？超时，用一个单调队列维护k长度的f值

代码

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [nums[0]] + [0] * (n-1)
        q = deque([0])

        for i in range(1, n):
            # 队头弹出什么
            if q and q[0] < i - k:
                q.popleft()
            f[i] = max(nums[i], f[q[0]] + nums[i])
            # 队尾弹出什么
            while q and f[q[-1]] <= f[i]:
                q.pop()
            q.append(i)
        
        return max(f)

总结

1. 对于这种选和不选的问题时，定义f[i]一般是考虑前i个值，且选择i时候的结果。