平衡子序列的最大和

标签: 树状数组 线段树 数组 二分查找 动态规划

难度: Hard

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

Submission

运行时间: 555 ms

内存: 40.9 MB

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        
        
        
        # my solution ... 600 ms ... 97 % ... 41.9 MB ... 42 %
        #  time: O(nlogn)
        # space: O(n)
        
        n = len(nums)
        pool = []        # pool keeps increasing of v-i
        emax = {}        # emax[v-i] = max_sum{v0, v1, v2, ... v} for v0-0 <= v1-1 <= v2-2 <= ... <= v-i
        res = float('-inf')
        for idx, num in enumerate(nums):
            i = bisect.bisect_right(pool, num-idx)
            
            cur = num
            if i:
                cur = max(emax[pool[i-1]] + num, cur)
            
            if num-idx not in emax:
                emax[num-idx] = cur
            else:
                emax[num-idx] = max(emax[num-idx], cur)
            
            res = max(res, cur)
            
            j = i
            while j < len(pool) and emax[num-idx] >= emax[pool[j]]:    # pool 递增同时，emax[pool[i]] 也需保持递增
                j += 1
            pool[i:j] = [num-idx]
        return res

Explain

该题解采用了动态规划的思路。首先，每个元素的值与其下标之差（num - idx）被使用来确定该元素能否成为平衡子序列的一部分。我们维护一个pool数组，它保存所有考虑过的num-idx的值，并保持递增顺序。同时，我们使用一个字典emax来存储每个不同的num-idx值所能达到的最大子序列和。遍历数组nums时，我们检查当前num-idx能插入pool的位置，并更新当前元素的最大可能序列和，同时更新emax。最后，我们在整个遍历过程中追踪可能的最大和。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        n = len(nums)
        pool = []        # pool keeps track of num-idx in increasing order
        emax = {}        # emax[num-idx] stores the maximum subsequence sum for each num-idx
        res = float('-inf')
        for idx, num in enumerate(nums):
            i = bisect.bisect_right(pool, num-idx)  # Find the right position to keep pool sorted
            cur = num  # Start with current number
            if i:
                cur = max(emax[pool[i-1]] + num, cur)  # Update max sum using previous maxes if possible
            if num-idx not in emax:
                emax[num-idx] = cur  # Initialize if not present
            else:
                emax[num-idx] = max(emax[num-idx], cur)  # Update emax for current num-idx
            res = max(res, cur)  # Update result
            j = i
            while j < len(pool) and emax[num-idx] >= emax[pool[j]]:  # Maintain increasing order in emax values
                j += 1
            pool[i:j] = [num-idx]  # Update pool to include only necessary elements
        return res

Explore

在这个问题中，使用每个元素的值减去其下标（num - idx）的操作是用来确定哪些元素可以形成一个平衡子序列。如果两个元素的num-idx值相同，那么这两个元素之间的序列可能是平衡的。这是因为如果num1-idx1等于num2-idx2，那么num1-num2等于idx1-idx2，即元素的增量相等于下标的增量，这是平衡序列的一个特征。通过这种方式，可以更容易地通过动态规划构建出最大的平衡子序列和。

状态转移方程的定义基于最优子结构的概念。在这里，`cur`代表以当前元素num结尾的最大平衡子序列和。`emax[pool[i-1]]`代表在当前元素之前，且具有小于或等于当前num-idx值的最大子序列和。如果存在这样的子序列，那么当前元素可以加入该子序列来可能形成一个更大的和。因此，状态转移方程`cur = max(emax[pool[i-1]] + num, cur)`表示考虑将当前元素加入前一个有效子序列或单独作为一个子序列的两种情况，取两者的最大值。

虽然二分查找可以高效地找到插入位置以保持pool的有序性，但在更新pool和emax时使用线性搜索可能降低效率，特别是在数组长度较大时。线性搜索导致的时间复杂度可能达到O(n^2)。一种更高效的方法可能是使用数据结构如平衡二叉搜索树（如红黑树）或跳表来同时维持pool的有序性和高效地更新emax，这样每次插入和更新的操作平均时间复杂度都可以保持在O(log n)。

在字典emax中，如果num-idx键已存在，则检查当前计算的子序列和是否大于已存储的值，如果大于，则进行更新。如果键不存在，则添加新的键值对。这种策略的优势在于可以确保每个num-idx值都对应其可能的最大子序列和，从而在遍历时能够获取到最优解。然而，这种策略的风险在于可能会存储大量的num-idx值，特别是对于大数组，这可能导致空间复杂度上升，同时更新操作可能会导致一定的时间开销。