列表

详情

1425. 带限制的子序列和

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

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

 

示例 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] 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int constrainedSubsetSum(vector<int>& nums, int k) { } };

golang 解法, 执行用时: 152 ms, 内存消耗: 9.2 MB, 提交时间: 2023-09-24 23:12:52 

// 请你返回 非空 子序列元素和的最大值
// dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])
func constrainedSubsetSum(nums []int, k int) int {

    res := nums[0]
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    queue := []int{0}  // 保持单调递减

    for i := 1; i < len(nums); i++ {
        
        if queue[0] < i - k {
            queue = queue[1:]
        }

        dp[i] = max(nums[i], dp[queue[0]]+nums[i])

        for len(queue) > 0 && dp[queue[len(queue)-1]] < dp[i] {
            queue = queue[:len(queue)-1]
        }

        queue = append(queue, i)
        res = max(res, dp[i])
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

cpp 解法, 执行用时: 228 ms, 内存消耗: 117.4 MB, 提交时间: 2023-09-24 23:12:14 

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        // 存储动态规划结果的数组
        vector<int> f(n);
        // 我们直接放入 f[0] 的值，防止处理边界情况
        f[0] = nums[0];
        // 单调队列
        deque<int> q;
        // 一开始唯一的 j 为 0
        q.push_back(0);
        
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            // 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出
            while (!q.empty() && i - q.front() > k) {
                q.pop_front();
            }
            // 此时队首的 j 即为最优的 j 值
            f[i] = max(f[q.front()], 0) + nums[i];
            ans = max(ans, f[i]);
            // 维护队列的单调性，不断从队尾弹出元素
            while (!q.empty() && f[i] >= f[q.back()]) {
                q.pop_back();
            }
            // 将 i 作为之后的新 j 值放入队尾
            q.push_back(i);
        }
        return ans;
    }
};

java 解法, 执行用时: 37 ms, 内存消耗: 55.2 MB, 提交时间: 2023-09-24 23:12:03 

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] f = new int[n];
        f[0] = nums[0];
        Deque<Integer> q = new ArrayDeque<Integer>();
        q.addLast(0);
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            // 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出
            while (!q.isEmpty() && i - q.peekFirst() > k) {
                q.removeFirst();
            }
            // 此时队首的 j 即为最优的 j 值
            f[i] = Math.max(f[q.peekFirst()], 0) + nums[i];
            ans = Math.max(ans, f[i]);
            // 维护队列的单调性，不断从队尾弹出元素
            while (!q.isEmpty() && f[i] >= f[q.peekLast()]) {
                q.removeLast();
            }
            // 将 i 作为之后的新 j 值放入队尾
            q.addLast(i);
        }
        return ans;
    }
}

python3 解法, 执行用时: 544 ms, 内存消耗: 28.6 MB, 提交时间: 2023-09-24 23:11:51 

'''
f[i] 表示在数组的前 i 个数中进行选择，并且恰好选择了第 i 个数，可以得到的最大和。
'''
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 存储动态规划结果的数组
        # 我们直接放入 f[0] 的值，防止处理边界情况
        f = [nums[0]] + [0] * (n - 1)
        # 单调队列
        # 一开始唯一的 j 为 0
        q = collections.deque([0])
        
        ans = nums[0]
        for i in range(1, n):
            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出
            while q and i - q[0] > k:
                q.popleft()
            # 此时队首的 j 即为最优的 j 值
            f[i] = max(f[q[0]], 0) + nums[i]
            ans = max(ans, f[i])
            # 维护队列的单调性，不断从队尾弹出元素
            while q and f[i] >= f[q[-1]]:
                q.pop()
            # 将 i 作为之后的新 j 值放入队尾
            q.append(i)
        return ans

上一题

© 2024 leetcode.cn