C++二分算法：平衡子序列的最大和-CSDN博客

涉及知识点

二分
动态规划
#题目
给你一个下标从 0 开始的整数数组 nums 。
nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < … < ik-1 如果这个子序列满足以下条件我们说它是 平衡的
对于范围 [1, k - 1] 内的所有 j nums[ij] - nums[ij-1] >= ij - ij-1 都成立。
nums 长度为 1 的 子序列 是平衡的。
请你返回一个整数表示 nums 平衡 子序列里面的 最大元素和 。
一个数组的 子序列 指的是从原数组中删除一些元素也可能一个元素也不删除后剩余元素保持相对顺序得到的 非空 新数组。
示例 1
输入nums = [3,3,5,6]
输出14
解释这个例子中选择子序列 [3,5,6] 下标为 0 2 和 3 的元素被选中。
nums[2] - nums[0] >= 2 - 0 。
nums[3] - nums[2] >= 3 - 2 。
所以这是一个平衡子序列且它的和是所有平衡子序列里最大的。
包含下标 1 2 和 3 的子序列也是一个平衡的子序列。
最大平衡子序列和为 14 。
示例 2
输入nums = [5,-1,-3,8]
输出13
解释这个例子中选择子序列 [5,8] 下标为 0 和 3 的元素被选中。
nums[3] - nums[0] >= 3 - 0 。
所以这是一个平衡子序列且它的和是所有平衡子序列里最大的。
最大平衡子序列和为 13 。
示例 3
输入nums = [-2,-1]
输出-1
解释这个例子中选择子序列 [-1] 。
这是一个平衡子序列而且它的和是 nums 所有平衡子序列里最大的。
参数范围
1 <= nums.length <= 105
-109 <= nums[i] <= 109

分析

时间复杂度

O(nlogn)。枚举子序列末尾时间复杂度O(n)。每次枚举需要几次二分查找时间复杂度O(logn)。
注意
删除被淘汰的元素总时间复杂度是O(n)因为每个元素顶多被删除一次。

原理

构建健康子序列的方式

示例3说明排除空子序列。排除空子序列后则必定有结尾元素我们枚举结尾元素。

长度为1的子序列	只有nums[ij]
长度大于1的子序列	以nums[j]的子序列+nums[ij]

nums[ij] - nums[ij-1] >= ij - ij-1 也就是nums[ij]-ij >= nums[ij-1]-(ij-1)。令 iSub=nums[ij]-ij,llSum是以ij结尾的健康子系列最大和。
如果iSub[i]<iSu[j]且llSum[i]>=llSum[j]则j被淘汰。能选择j则一定可以选择i而llSum[i]大于等于llSum[j]。淘汰后,llSub和llSum都按升序排序。寻找llSub 小于等于当前llSub的最大llSub对应的llSumllSum+nums[i] 就是方式二的最大值由于llSum可能为负数所以方式二不一定比方式一大。
插入iSub时需要删除被iSub淘汰的数据。

当前iSub一定不会被淘汰

令j < i如果nums[j] - j <= nums[i]-i。==> nums[j]+(i-j) <= nums[i]
因为 (i-j)>0所以nums[j] < nums[i]。假定以nums[j]结尾的最大子序列为{…,nums[j]}它的和一定小于{…,nums[i]}。

代码

核心代码

class Solution {
public:
long long maxBalancedSubsequenceSum(vector& nums) {
std::map<int, long long> mSubSum;
auto Add =[&](int iSub, long long llCur)
{
auto it = mSubSum.upper_bound(iSub);
long long llSum = llCur;
if (mSubSum.begin() != it)
{
if (std::prev(it)->second > 0)
{
llSum += std::prev(it)->second;
}
}
it = mSubSum.lower_bound(iSub);
auto ij = it;
for (; (ij != mSubSum.end()) && (ij->second <= llSum); ++ij);
mSubSum.erase(it, ij);
if (!mSubSum.count(iSub))
{
mSubSum[iSub] = llSum;
}
};
for (int i = 0; i < nums.size(); i++)
{
Add(nums[i] - i, nums[i]);
}
return mSubSum.rbegin()->second;
}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
Solution slu;
long long res;
vector nums;
nums = { -3,-1 };
res = slu.maxBalancedSubsequenceSum(nums);
Assert(res, -1LL);
nums = { -2,-1 };
res = slu.maxBalancedSubsequenceSum(nums);
Assert(res,-1LL);
nums = { 3, 3, 5, 6 };
res = slu.maxBalancedSubsequenceSum(nums);
Assert(res, 14LL);;

//CConsole::Out(res);

}

优化

	if (!mSubSum.count(iSub))
			{
				mSubSum[iSub] = llSum;
			}

中的if条件可以删除

扩展阅读

视频课程

有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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