1425. 带限制的子序列和
给你一个整数数组
nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
示例 1：
输出：37 解释：子序列为 [10, 2, 5, 20] 。
示例 2：
输入：nums = [-1,-2,-3], k = 1 输出：-1 解释：子序列必须是非空的，所以我们选择最大的数字。
示例 3：
输入：nums = [10,-2,-10,-5,20], k = 2 输出：23 解释：子序列为 [10, -2, -5, 20] 。
提示：
1 <= k <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4
通过次数3,605提交次数8,024
法 1 动态规划
思路
dp[i] 为 以 nums[i] 结尾的 最大子序列和
dp[i] = nums[i] + max(max(dp[i-k:i]), 0)
dp[i-k:i] 即为最近的 k 个结果。
题解
class Solution: def constrainedSubsetSum(self, nums: List[int], k: int) -> int: n = len(nums) dp = [0] * n dp[0] = nums[0] for i in range(1, n): temp = dp[i-k:i] if i-k >= 0 else dp[:i] dp[i] = nums[i] + max(max(temp) , 0) return max(dp)
法 2 动态规划 + 单调队列
思路
用单调队列来实现 dp 中最近的 k 个值的最大值
class Solution: def constrainedSubsetSum(self, nums: List[int], k: int) -> int: n = len(nums) dp = [0] * n queue = deque() dp[0] = nums[0] for i in range(0, n-1): # 维持长度为 k 的队列 while queue and i - queue[0] >= k: queue.popleft() # 维持递减队列 while queue and dp[i] >= dp[queue[-1]]: queue.pop() queue.append(i) dp[i+1] = nums[i+1] + max(0, dp[queue[0]]) return max(dp)
法 3 动态规划 + 优先队列
思路
采用优先队列来 实现 dp 中最近的 k 个值的最大值
题解
class Solution: def constrainedSubsetSum(self, nums: List[int], k: int) -> int: n = len(nums) dp = [0] * n dp[0] = nums[0] queue = [] for i in range(0, n-1): # 维持长度为 k 的队列 ：加上 dp[i]长度为 k while queue and i - queue[0][1] >= k: heapq.heappop(queue) heapq.heappush(queue, (-dp[i], i)) dp[i+1] = nums[i+1] + max(0, dp[queue[0][1]]) return max(dp)