平衡子序列的最大和

序列的最大和"/>

平衡子序列的最大和

给你一个下标从 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

题解：
我们可以考虑把式子改变一下：

// nums[i] - nums[j] >= i - j

// nums[i] - i >= nums[j] - j

// b[i] = nums[i] - i

  上升子序列  max

  f[i]  = 以小标 i 结尾的子序列 对应的nums的最大值

    ans = max(f)

    f[i] = f[j] + nums[i]

    j < i && b[j] < b[i]

用记录其数组前的以i结尾数符合条件的最大值。

class N{vector<long long> tree;public:N(int n):tree(n,LLONG_MIN){}void update(int i,long long val){while(i < tree.size()){tree[i] = max(tree[i],val);i += i & -i;}}long long pre_max(int i){long long res = LLONG_MIN;while(i > 0){res = max(res,tree[i]);i &=i-1; //去掉最后一个1}return res;}
};
class Solution {
// nums[i] - nums[j] >= i - j
// nums[i] - i >= nums[j] - j
// b[i] = nums[i] - i
/*上升子序列  maxf[i]  = 以小标 i 结尾的子序列 对应的nums的最大值 ans = max(f)f[i] = f[j] + nums[i]j < i && b[j] < b[i]*/
public: long long maxBalancedSubsequenceSum(vector<int>& nums) {int n = nums.size();vector<int> b(n+1);for(int i = 0;i < n;i++){b[i] = nums[i] - i;}sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());long long ans = LLONG_MIN;N t = N(b.size()+1);for(int i = 0;i < n;i++){int j = lower_bound(b.begin(),b.end(),nums[i] - i) - b.begin()+1;long long f = max(t.pre_max(j),0LL) + nums[i];ans = max(ans , f);t.update(j,f);}return ans;}
};