自己做网站挂广告,建设企业和建筑企业,免费在线网站建设,做音乐网站没有版权本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个整数数组 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] 。提示
1 k nums.length 10^5-10^4 nums[i] 10^4 解法 动态规划单调队列优化
我们用 f ( i ) f(i) f(i) 表示在数组的前 i i i 个数中进行选择并且恰好选择了第 i i i 个数可以得到的最大和。那么 f ( i ) f(i) f(i) 的状态转移分为两种
如果我们在前 i i i 个数中只选择了 n u m s [ i ] nums[i] nums[i] 那么和即为 f [ i ] nums [ i ] f[i] \textit{nums}[i] f[i]nums[i]如果我们还选择了其它的数那么我们可以枚举上一个选择的数 n u m s [ j ] nums[j] nums[j] 并通过 f [ j ] f[j] f[j] 进行状态转移。具体地根据题目的要求相邻两个被选择的整数在数组中的下标之差必须小于等于 k k k 也就是 0 i − j ≤ k 0 i - j \leq k 0i−j≤k 因此可以写出如下的状态转移方程 f [ i ] max max ( i − k , 0 ) ≤ j i ( f [ j ] ) nums [ i ] f[i] \max_{\max(i-k, 0) \leq j i}(f[j]) \textit{nums}[i] f[i]max(i−k,0)≤jimax(f[j])nums[i]
将两种情况写在一起就可以得到状态转移方程 f [ i ] max ( max max ( i − k , 0 ) ≤ j i ( f [ j ] ) , 0 ) nums [ i ] f[i] \max\left(\max_{\max(i-k, 0) \leq j i}(f[j]), 0\right) \textit{nums}[i] f[i]max(max(i−k,0)≤jimax(f[j]),0)nums[i] 这个状态转移方程看上去很吓人但我们可以从最简单的方法开始想起。对于每一个 f ( i ) f(i) f(i)我们只要枚举与 i i i 的差值是否小于等于 k k k 的所有 j j j 并在这些 j j j 中选择一个最大的 f [ j ] f[j] f[j] 进行状态转移即可。如果最大的 f [ j ] f[j] f[j] 小于 0 0 0 那么我们不进行状态转移只选择 n u m s [ i ] nums[i] nums[i] 。
然而这样做的时间复杂度为 O ( n k ) O(nk) O(nk) 会超出时间限制因为枚举 i i i 和 j j j 的时间复杂度分别为 O ( n ) O(n) O(n) 和 O ( k ) O(k) O(k) 。那么我们如何进行优化呢
观察上面的状态转移方程我们大致有一个这样的想法对于每一个 i i i我们选择的都是满足要求的 j j j 中最大的 f [ j ] f[j] f[j] 值。那么如果 f ( i ) f(i) f(i) 是从 f [ j ] f[j] f[j] 转移而来的只要 j j j 与 i 1 i1 i1 相差不超过 k k k f [ i 1 ] f[i1] f[i1] 也很有可能从 f [ j ] f[j] f[j] 转移而来。
这个想法也就是我们熟知的「单调栈」或者「单调队列」。不妨试着使用它们对状态转移方程进行优化。
单调队列优化
在从小到大枚举 i i i 的过程中假设我们有两个位置 j 1 j_1 j1 和 j 2 j_2 j2 可以考虑进行转移并且 j 1 j 2 j_1 j_2 j1j2 。如果 f [ j 1 ] ≤ f [ j 2 ] f[j_1] \leq f[j_2] f[j1]≤f[j2] 那么我们可以断定对于以后会枚举到的所有 i i i j 1 j_1 j1 都不会优于 j 2 j_2 j2 了。换句话说我们可以直接「扔掉」 j 1 j_1 j1 因为它不会转移到后续的任何状态。
这是为什么呢我们这样想对于任意一个满足 j 1 j 2 i j_1 j_2 i j1j2i 的 i i i 如果它从 j 1 j_1 j1 转移而来那么它一定也能从 j 2 j_2 j2 转移而来这是因为转移的唯一要求是 i i i 和 j j j 相差不超过 k k k 那么在 i i i 和 j 1 j_1 j1 满足要求的前提下 i i i 和 j 2 j_2 j2 也一定满足要求。并且 f [ j 1 ] ≤ f [ j 2 ] f[j_1] \leq f[j_2] f[j1]≤f[j2] 那么 j 2 j_2 j2 一定不比 j 1 j_1 j1 差。那么在「有生之年」我们在进行转移时就不需要考虑 j 1 j_1 j1 了。
因此我们可以考虑使用一个「单调栈」来维护所有可能会考虑的 j j j 。为什么它是一个「栈」呢我们来看看它的具体维护方法
假设我们当前维护了这样的一个「单调栈」它包含 j 1 , j 2 , ⋯ , j x j_1, j_2, \cdots, j_x j1,j2,⋯,jx 并且 j 1 j 2 ⋯ j x j_1 j_2 \cdots j_x j1j2⋯jx 。根据上面提到的性质必定有 f [ j 1 ] f [ j 2 ] ⋯ f [ j x ] f[j_1] f[j_2] \cdots f[j_x] f[j1]f[j2]⋯f[jx] 。如果我们需要将一个新的 j j j 值 j y j_y jy 放入单调栈中那么我们从栈顶元素开始考虑如果 f [ j x ] ≤ f [ j y ] f[j_x] \leq f[j_y] f[jx]≤f[jy] 那么根据上文的推导我们可以直接「扔掉」 j x j_x jx 也就是将栈顶元素弹出。以此类推我们可以不断地弹出栈顶元素直到栈顶元素对应的 f f f 值大于 f [ j y ] f[j_y] f[jy] 或者栈为空。此时我们再将 j y j_y jy 放入栈顶就得到了一个新的「单调栈」。这样以来栈底的 j j j 对应着最大的 f [ j ] f[j] f[j] 值我们用它来转移到 f ( i ) f(i) f(i) 就行了。
然而这样的设计存在两个问题
我们使用的是一个「栈」在仅使用栈的 API 的前提下而我们并没有办法获得「栈底」的元素栈底的 j j j 可能与当前的 i i i 值的差大于 k k k 。
因此我们需要用「队列」来代替栈即单调队列。
对于第一个问题我们可以通过获取队首元素解决。对于第二个问题我们要做的是不断地将队首的元素弹出直到队首的 j j j 与当前的 i i i 值的差小于 k k k 为止。由于我们需要「取出队首元素」「取出队尾元素」这两种操作因此我们使用的是「双端队列」。
算法流程——我们使用单调队列进行优化的动态规划的算法流程如下
我们用一个双端队列来维护所有可能会进行转移的 j j j 值。在队列中这些 j j j 值单调递增但是它们对应的 f [ j ] f[j] f[j] 值是单调递减的我们从小到大枚举 i i i 。在枚举的每一步中单调队列的队首元素就是最优的转移选择。但由于题目要求相邻的两个数的位置最多间隔 k k k 因此我们需要从队首弹出元素直到队首的 j j j 值与 i i i 的差值小于等于 k k k 在计算出 f ( i ) f(i) f(i) 后我们将 i i i 根据规则放入单调队列的队尾。在放入之前可能会弹出若干队尾的元素。最终的答案即为所有 f ( i ) f(i) f(i) 中的最大值。
class Solution {
public:int constrainedSubsetSum(vectorint nums, int k) {int n nums.size();// 存储动态规划结果的数组vectorint f(n);// 我们直接放入f[0]的值防止处理边界情况f[0] nums[0];// 单调队列dequeint q;// 一开始唯一的j为0q.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;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 其中 n n n 是数组 nums \textit{nums} nums 的长度。每一个数组下标都被放入队列一次并且被弹出队列最多一次因此处理队列的时间总计为 O ( n ) O(n) O(n) 与枚举 i i i 的时间 O ( n ) O(n) O(n) 相加仍然为 O ( n ) O(n) O(n) 。空间复杂度 O ( n ) O(n) O(n) 数组 f f f 和单调队列各需要 O ( n ) O(n) O(n) 的空间。
