Hard

题目描述

给你一个下标从 0 开始的整数数组 nums。

nums 的一个长度为 k 且下标为 i0 < i1 < ... < ik-1 的 子序列 是 平衡的 ，当且仅当对于每个在 [1, k - 1] 范围内的 j ，都有 nums[ij] - nums[ij-1] >= ij - ij-1 。

长度为 1 的 nums 子序列是平衡的。

返回一个表示 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] 。
这是一个平衡的子序列，其和是平衡子序列中的最大值。

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题的关键在于理解平衡子序列的条件，并将其转化为可以用数据结构优化的形式。

首先分析平衡条件：对于子序列中相邻的两个元素 nums[i] 和 nums[j]（其中 i < j），需要满足 nums[j] - nums[i] >= j - i。

将不等式变形：nums[j] - j >= nums[i] - i。这个变形非常关键，它告诉我们对于每个位置 i，我们可以计算一个值 nums[i] - i，平衡条件就是后面元素的这个值要大于等于前面元素的值。

基于这个观察，我们可以使用动态规划：设 dp[i] 表示以位置 i 结尾的平衡子序列的最大和。转移方程为：

  • dp[i] = max(nums[i], max{dp[j] + nums[i] | j < i 且 nums[j] - j <= nums[i] - i})

朴素实现的时间复杂度是 O(n²)，对于本题的数据规模会超时。我们需要优化查询过程。

优化思路： 使用线段树或树状数组来维护 dp 值。由于 nums[i] - i 的值域很大，需要进行坐标压缩。我们按照 nums[i] - i 的值建立映射，然后用线段树维护每个值对应的最大 dp 值。

对于每个位置 i，我们查询所有 nums[j] - j <= nums[i] - i 的位置中 dp 值的最大值，然后更新当前位置的 dp 值。

推荐解法： 使用线段树 + 坐标压缩的方法，时间复杂度 O(n log n)。

代码实现

class Solution {
public:
    long long maxBalancedSubsequenceSum(vector<int>& nums) {
        int n = nums.size();
        vector<long long> vals;
        
        // 收集所有可能的 nums[i] - i 值
        for (int i = 0; i < n; i++) {
            vals.push_back((long long)nums[i] - i);
        }
        
        // 排序并去重，进行坐标压缩
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        
        int m = vals.size();
        vector<long long> tree(4 * m, LLONG_MIN / 2);
        
        function<void(int, int, int, int, long long)> update = [&](int v, int tl, int tr, int pos, long long val) {
            if (tl == tr) {
                tree[v] = max(tree[v], val);
            } else {
                int tm = (tl + tr) / 2;
                if (pos <= tm) {
                    update(2 * v, tl, tm, pos, val);
                } else {
                    update(2 * v + 1, tm + 1, tr, pos, val);
                }
                tree[v] = max(tree[2 * v], tree[2 * v + 1]);
            }
        };
        
        function<long long(int, int, int, int, int)> query = [&](int v, int tl, int tr, int l, int r) -> long long {
            if (l > r) return LLONG_MIN / 2;
            if (l == tl && r == tr) {
                return tree[v];
            }
            int tm = (tl + tr) / 2;
            return max(query(2 * v, tl, tm, l, min(r, tm)),
                      query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        };
        
        long long ans = LLONG_MIN;
        
        for (int i = 0; i < n; i++) {
            long long val = (long long)nums[i] - i;
            int pos = lower_bound(vals.begin(), vals.end(), val) - vals.begin();
            
            long long maxPrev = query(1, 0, m - 1, 0, pos);
            long long dp = nums[i];
            if (maxPrev > LLONG_MIN / 2) {
                dp = max(dp, maxPrev + nums[i]);
            }
            
            update(1, 0, m - 1, pos, dp);
            ans = max(ans, dp);
        }
        
        return ans;
    }
};

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 收集所有可能的 nums[i] - i 值并进行坐标压缩
        vals = sorted(set(nums[i] - i for i in range(n)))
        m = len(vals)
        
        # 线段树
        tree = [float('-inf')] * (4 * m)
        
        def update(v, tl, tr, pos, val):
            if tl == tr:
                tree[v] = max(tree[v], val)
            else:
                tm = (tl + tr) // 2
                if pos <= tm:
                    update(2 * v, tl, tm, pos, val)
                else:
                    update(2 * v + 1, tm + 1, tr, pos, val)
                tree[v] = max(tree[2 * v], tree[2 * v + 1])
        
        def query(v, tl, tr, l, r):
            if l > r:
                return float('-inf')
            if l == tl and r == tr:
                return tree[v]
            tm = (tl + tr) // 2
            return max(query(2 * v, tl, tm, l, min(r, tm)),
                      query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r))
        
        ans = float('-inf')
        
        for i in range(n):
            val = nums[i] - i
            pos = bisect.bisect_left(vals, val)
            
            max_prev = query(1, 0, m - 1, 0, pos)
            dp = nums[i]
            if max_prev != float('-inf'):
                dp = max(dp, max_prev + nums[i])
            
            update(1, 0, m - 1, pos, dp)
            ans = max(ans, dp)
        
        return ans

public class Solution {
    public long MaxBalancedSubsequenceSum(int[] nums) {
        int n = nums.Length;
        
        // 收集所有可能的 nums[i] - i 值
        var vals = new List<long>();
        for (int i = 0; i < n; i++) {
            vals.Add((long)nums[i] - i);
        }
        
        // 排序并去重，进行坐标压缩
        vals.Sort();
        vals = vals.Distinct().ToList();
        
        int m = vals.Count;
        var tree = new long[4 * m];
        Array.Fill(tree, long.MinValue / 2);
        
        void Update(int v, int tl, int tr, int pos, long val) {
            if (tl == tr) {
                tree[v] = Math.Max(tree[v], val);
            } else {
                int tm = (tl + tr) / 2;
                if (pos <= tm) {
                    Update(2 * v, tl, tm, pos, val);
                } else {
                    Update(2 * v + 1, tm + 1, tr, pos, val);
                }
                tree[v] = Math.Max(tree[2 * v], tree[2 * v + 1]);
            }
        }
        
        long Query(int v, int tl, int tr, int l, int r) {
            if (l > r) return long.MinValue / 2;
            if (l == tl && r == tr) {
                return tree[v];
            }
            int tm = (tl + tr) / 2;
            return Math.Max(Query(2 * v, tl, tm, l, Math.Min(r, tm)),
                           Query(2 * v + 1, tm + 1, tr, Math.Max(l, tm + 1), r));
        }
        
        long ans = long.MinValue;
        
        for (int i = 0; i < n; i++) {
            long val = (long)nums[i] - i;
            int pos = vals.BinarySearch(val);
            
            long maxPrev = Query(1, 0, m - 1, 0, pos);
            long dp = nums[i];
            if (maxPrev > long.MinValue / 2) {
                dp = Math.Max(dp, maxPrev + nums[i]);
            }
            
            Update(1, 0, m - 1, pos, dp);
            ans = Math.Max(ans, dp);
        }
        
        return ans;
    }
}

var maxBalancedSubsequenceSum = function(nums) {
    const n = nums.length;
    const pairs = [];
    
    for (let i = 0; i < n; i++) {
        pairs.push([nums[i] - i, nums[i]]);
    }
    
    pairs.sort((a, b) => a[0] - b[0]);
    
    const fenwick = new Array(n + 1).fill(-Infinity);
    
    function update(idx, val) {
        for (let i = idx; i <= n; i += i & -i) {
            fenwick[i] = Math.max(fenwick[i], val);
        }
    }
    
    function query(idx) {
        let max = -Infinity;
        for (let i = idx; i > 0; i -= i & -i) {
            max = Math.max(max, fenwick[i]);
        }
        return max;
    }
    
    let result = -Infinity;
    
    for (let i = 0; i < n; i++) {
        const [transformedVal, originalVal] = pairs[i];
        
        let maxPrev = query(i);
        let currentSum = originalVal;
        
        if (maxPrev !== -Infinity) {
            currentSum = Math.max(currentSum, maxPrev + originalVal);
        }
        
        result = Math.max(result, currentSum);
        update(i + 1, currentSum);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)坐标压缩需要 O(n log n)，每次线段树操作需要 O(log n)
空间复杂度O(n)线段树和坐标压缩数组的空间开销

相关题目