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说明，排除空子序列。排除空子序列后，则必定有结尾元素，我们枚举结尾元素。

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

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17