Hard

题目描述

给你一个整数数组 nums 和一个整数 k，请你返回 非空 子序列元素和的最大值，子序列需要满足：对于连续的两个元素 nums[i] 和 nums[j]，其中 i < j，这两个元素在原数组里的位置需要满足 j - i <= k。

数组的子序列定义为：通过删除数组中的一些元素（也可以不删除），剩余元素保持原来的顺序得到的数组。

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：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

解题思路

这是一道经典的动态规划 + 单调队列优化题目。核心思想是使用动态规划求解，并利用单调队列优化时间复杂度。

思路分析：

  1. 动态规划状态定义：定义 dp[i] 表示以位置 i 结尾的子序列的最大和。

  2. 状态转移方程：对于位置 i，我们有两种选择：

    • 单独选择 nums[i] 作为子序列
    • 从前面 k 个位置中选择一个最大的 dp 值，加上 nums[i]

    因此：dp[i] = nums[i] + max(0, max(dp[i-k], dp[i-k+1], ..., dp[i-1]))

  3. 优化思路：朴素的动态规划需要 O(n×k) 的时间复杂度，我们可以使用单调双端队列来维护滑动窗口内的最大值，将时间复杂度优化到 O(n)。

  4. 单调队列维护：

    • 队列存储下标，按照 dp 值单调递减排列
    • 当窗口滑动时，移除超出范围的元素
    • 队首始终是当前窗口内 dp 值最大的位置

这种方法既保证了正确性，又将时间复杂度优化到了最佳。

代码实现

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);
        deque<int> dq;
        int result = nums[0];
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的元素
            while (!dq.empty() && dq.front() < i - k) {
                dq.pop_front();
            }
            
            // 计算当前位置的最大和
            dp[i] = nums[i];
            if (!dq.empty()) {
                dp[i] = max(dp[i], nums[i] + dp[dq.front()]);
            }
            
            // 维护单调队列，移除队尾较小的元素
            while (!dq.empty() && dp[dq.back()] <= dp[i]) {
                dq.pop_back();
            }
            
            // 只有当dp[i] > 0时才加入队列（对后续位置有贡献）
            if (dp[i] > 0) {
                dq.push_back(i);
            }
            
            result = max(result, dp[i]);
        }
        
        return result;
    }
};

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        from collections import deque
        
        n = len(nums)
        dp = [0] * n
        dq = deque()
        result = nums[0]
        
        for i in range(n):
            # 移除超出窗口范围的元素
            while dq and dq[0] < i - k:
                dq.popleft()
            
            # 计算当前位置的最大和
            dp[i] = nums[i]
            if dq:
                dp[i] = max(dp[i], nums[i] + dp[dq[0]])
            
            # 维护单调队列
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            
            # 只有当dp[i] > 0时才加入队列
            if dp[i] > 0:
                dq.append(i)
            
            result = max(result, dp[i])
        
        return result

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        int n = nums.Length;
        int[] dp = new int[n];
        var dq = new LinkedList<int>();
        int result = nums[0];
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的元素
            while (dq.Count > 0 && dq.First.Value < i - k) {
                dq.RemoveFirst();
            }
            
            // 计算当前位置的最大和
            dp[i] = nums[i];
            if (dq.Count > 0) {
                dp[i] = Math.Max(dp[i], nums[i] + dp[dq.First.Value]);
            }
            
            // 维护单调队列
            while (dq.Count > 0 && dp[dq.Last.Value] <= dp[i]) {
                dq.RemoveLast();
            }
            
            // 只有当dp[i] > 0时才加入队列
            if (dp[i] > 0) {
                dq.AddLast(i);
            }
            
            result = Math.Max(result, dp[i]);
        }
        
        return result;
    }
}

var constrainedSubsetSum = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n);
    const dq = [];
    let result = nums[0];
    
    for (let i = 0; i < n; i++) {
        // 移除超出窗口范围的元素
        while (dq.length > 0 && dq[0] < i - k) {
            dq.shift();
        }
        
        // 计算当前位置的最大和
        dp[i] = nums[i];
        if (dq.length > 0) {
            dp[i] = Math.max(dp[i], nums[i] + dp[dq[0]]);
        }
        
        // 维护单调队列
        while (dq.length > 0 && dp[dq[dq.length - 1]] <= dp[i]) {
            dq.pop();
        }
        
        // 只有当dp[i] > 0时才加入队列
        if (dp[i] > 0) {
            dq.push(i);
        }
        
        result = Math.max(result, dp[i]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：虽然有嵌套循环，但每个元素最多入队和出队一次，所以总时间复杂度是 O(n)
  • 空间复杂度：需要 O(n) 的 dp 数组和 O(k) 的单调队列空间，总体为 O(n)

相关题目