涉及知识点

二分
动态规划
#题目
给你一个下标从 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条件可以删除

相关下载

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

测试环境

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