使用fenwick树或位的数组中非递减子序列的最大和

Question

如何利用fenwick树求数组中一个非递减子序列的最大和？例如，我们有1 4 4 2 2 3 3 1，这里一个非递减子序列的最大和是11（1 2 2 3 3）。

Answer 1

可以使用动态规划算法找到最大和。扫描数组，对于每个元素，将其值添加到有效的最大子序列和（子序列以不大于该元素的值结束）。

高效的实现需要某种方法在给定的子范围内快速找到最大值。可以使用扩充的二叉搜索树来实现。Fenwick树正是扩充二叉搜索树的一种高效实现。Fenwick树最常见的用途是在某个子范围中找到一个值的和。简单的修改允许使用它来查找子范围最大值（这是有效的，因为在这个特定的情况下，Fenwick树中的值从不减少）。

有关详细信息，请参阅这段Python代码：

array = [1, 4, 4, 2, 2, 3, 3, 1]

numbers = sorted(set(array))
n = len(numbers)
indexes = {numbers[v]:v+1 for v in range(0, n)}
n += 1
bit = [0] * n
result = 0

for x in array:
    pos = indexes[x]
    i = pos
    maximum = 0
    while i != 0:
        maximum = max(maximum, bit[i])
        i = i & (i-1)
    x += maximum
    i = pos
    while i < n:
        bit[i] = max(bit[i], x)
        i += i & -i
    result = max(result, x)

print(result)

时间复杂度为O（N log N）。空间复杂度为O(N)。