题目
给你一个整数数组 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
单调队列
时间复杂度😮(n)
由于是非空子序列,所以一定有结尾。枚举子序列的结尾,对于每个下标i,有以下两种情况:
方式一 | 只有一个元素nums[i]的子系列 |
方式一 | 以nums[j]结尾的子序列,再加上nums[i] |
如果存在以nums[j]结尾的子序列,且其和为正则选择方法二,如果有多个j,取和最大的。
单调队列
vRet[i]是以nums[i]结尾的最大子系列和。
queIndex记录了[0,i) 淘汰以下两类下标:
一,下标小于i-k,从队尾淘汰。
二,j1
代码
核心代码
class Solution { public: int constrainedSubsetSum(vector<int>& nums, int k) { m_c = nums.size(); vector<int> vRet(m_c); std::deque<int> queIndex; for (int i = 0; i < m_c; i++) { if (queIndex.size() && (queIndex.front() < i - k)) { queIndex.pop_front(); } const int pre = (queIndex.size() ? vRet[queIndex.front()] : 0); vRet[i] = max(0, pre) + nums[i]; while (queIndex.size() && (vRet[queIndex.back()] <= vRet[i])) { queIndex.pop_back(); } queIndex.emplace_back(i); } return *std::max_element(vRet.begin(), vRet.end()); } int m_c; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; int k; { Solution sln; nums = { 10,2,-10,5,20 },k=2; auto res = sln.constrainedSubsetSum(nums,k); Assert(37, res); } { Solution sln; nums = { -1,-2,-3 }, k =1; auto res = sln.constrainedSubsetSum(nums, k); Assert(-1, res); } { Solution sln; nums = { 10,-2,-10,-5,20 }, k = 2; auto res = sln.constrainedSubsetSum(nums, k); Assert(23, res); } //CConsole::Out(res); }
2023年2月版
class Solution { public: int constrainedSubsetSum(vector<int>& nums, int k) { m_c = nums.size(); vector<int> indexs, maxs; int iHasDo = 0; for (int i = 0; i < nums.size(); i++ ) { const auto& num = nums[i]; while ((indexs.size() > iHasDo) && (i - indexs[iHasDo] > k)) { iHasDo++; } int iValue = ( maxs.size() == iHasDo) ? 0 : maxs[iHasDo]; iValue = max(iValue, 0) + num; while ((maxs.size() > iHasDo) && (iValue >= maxs.back())) { maxs.pop_back(); indexs.pop_back(); } indexs.push_back(i); maxs.push_back(iValue); } return *std::max_element(maxs.begin(), maxs.end()); } int m_c; };
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用C++ 实现。