非递减子序列在阵列中使用树状数组或位最大总和 [英] Maximum Sum of a non decreasing sub-sequence in an array using fenwick tree or BIT

问题描述

我们如何才能找到一个非递减子序列在使用树状数组的数组的最大一笔？例如，我们有1 4 4 2 2 3 3 1，这里一个非递减子序列的最大总和是11（1 2 2 3 3）。

How can we find the maximum sum of a non-decreasing sub-sequence in an array using fenwick tree? For example we have 1 4 4 2 2 3 3 1, here the maximum sum of a non-decreasing sub-sequence is 11 (1 2 2 3 3).

推荐答案

最高金额可使用动态规划算法来找到。扫描阵列和每个元素的值添加到最大的子序列总和这是有效的（亚序列，其值不大于该元素更大结束）。

Maximum sum may be found using a dynamic programming algorithm. Scan the array and for each element add its value to the largest sub-sequence sum which is valid (sub-sequence ends with a value not greater than this element).

高效的实现需要一些方法来快速查找特定子范围的最大值。扩充二进制搜索树可以用来做。树状数组仅仅是一个有效的实现扩充二叉搜索树。最常见的用途树状数组的是找到在某些子范围值的和。平凡的调整可以用它来寻找子范围最大（这个工程，因为在这种特殊情况下，在树状数组值永远不会降低）。

Efficient implementation needs some way to quickly find maximum value in given sub-range. Augmented binary search tree may be used to do it. Fenwick tree is just an efficient implementation of augmented binary search tree. Most common use of Fenwick tree is to find a sum of values in some sub-range. Trivial modification allows to use it to find sub-range maximum (this works because in this particular case values in the Fenwick tree are never decreased).

有关详细信息，请参阅本Python的code：

See this Python code for details:

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)

索引字典用于从最多输入数组的数组的大小减小树状数组的大小。首先嵌套的，而找到子范围最大的树状数组。第二个嵌套的，而更新树状数组的款项中的一个更新后。

indexes dictionary is used to decrease size of Fenwick tree from the largest number in the input array to the array's size. First nested while finds sub-range maximum in Fenwick tree. Second nested while updates Fenwick tree after one of the sums is updated.

这code仅适用于正数的​​数组。在一般情况下，输入数组应pre-处理过滤掉所有非正数。

This code works only for an array of positive numbers. In general case input array should be pre-processed by filtering out all non-positive numbers.

时间复杂度为O（N日志N）。空间复杂度为O（N）。

Time complexity is O(N log N). Space complexity is O(N).

这篇关于非递减子序列在阵列中使用树状数组或位最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！