Manjusaka

10-21 leetcode 1425

链接 1425. Constrained Subsequence Sum

题目

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.

题解

这题看到子序列，最大和几个关键词，起手可以先推一个公式

dp[i]=max(nums[i], dp[j] + nums[i]) for j in range(i - k, i)

直接的时间复杂度是 O(nk), 考虑到这题官方的数据范围，只能说 10^10 的最坏复杂度直接 TLE 了

那么我们能不能减少时间复杂度呢？

我们看到这题一个核心可以越过最多不超过 k 个元素来选择子序列，那么这个时候可以考虑一个滑动窗口+单调队列来处理

1. 维护一个单调递减队列，队列中存储下标，如果队头超出 k 范围则队头出列
2. 然后我们 dp[i] = max(dp[i], dp[队头] + nums[i])
3. 因为是单调递减队列，如果 nums[i] > nums[队尾]，那么队尾出列，因为队尾的位置确定不会属于状态转移的范围。

from collections import deque


class Solution:
    def constrainedSubsetSum(self, nums: list[int], k: int) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        queue = deque([0])
        result = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[queue[0]])
            result = max(result, dp[i])
            while queue and queue[0] < i - k + 1:
                queue.popleft()
            while queue and dp[queue[-1]] <= dp[i]:
                queue.pop()
            queue.append(i)
        return result