题目描述

给你一个整数数组 nums 和一个整数 k，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j]，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

样例

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20]。

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

输入：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

算法

(动态规划，单调队列) $O(n)$

1. 设 $f(i)$ 表示以位置 $i$ 为结尾的子序列的最大值。
2. 初始时 $f(0) = nums(0)$，其余待定。
3. 转移时，$f(i)$ 可以只包含 $nums(i)$，也可以选择 $f(j), j \in [i-k, i-1]$。
4. 最终答案为 $\max(f(i))$。
5. 但暴力做的时间复杂度是 $O(nk)$ 的，考虑用单调队列优化。
6. 维护一个单调递减的队列，队列中存储下标，队头为最大值的下标。每次如果队头超出了范围 $i-k$，则队头出队。
7. 此时 $f(i)$ 可以选择队头的值加上 $nums(i)$，也可以仅选择 $nums(i)$。
8. 然后位置 $i$ 入队，入队时，如果当前的值大于等于队尾，则队尾永远都不会有机会作为最大值被转移，则队尾出队直到插入 $i$ 后队列单调递减。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，每个位置最多进队一次，出队一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储状态和队列。

C++ 代码

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n);

        deque<int> q;
        int ans = nums[0];

        f[0] = nums[0];
        q.push_back(0);

        for (int i = 1; i < n; i++) {
            while (!q.empty() && i - q.front() > k)
                q.pop_front();

            f[i] = max(nums[i], f[q.front()] + nums[i]);
            ans = max(ans, f[i]);

            while (!q.empty() && f[i] >= f[q.back()])
                q.pop_back();

            q.push_back(i);
        }
        return ans;
    }
};