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

涉及知识点

二分
动态规划
#题目
给你一个下标从 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对应的llSum，llSum+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

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛