我们如何使用芬威克树找到数组中非递减子序列的最大和?例如我们有 1 4 4 2 2 3 3 1,这里一个非递减子序列的最大和是 11 (1 2 2 3 3)。
最佳答案
可以使用动态规划算法找到最大和。扫描数组并将每个元素的值添加到有效的最大子序列和(子序列以不大于该元素的值结束)。
高效的实现需要一些方法来快速找到给定子范围内的最大值。可以使用增强二叉搜索树来做到这一点。 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)
indexes
字典用于将 Fenwick 树的大小从输入数组中的最大数减小到数组的大小。首先嵌套 while
在 Fenwick 树中找到子范围最大值。第二个嵌套 while
在其中一个和更新后更新 Fenwick 树。
此代码仅适用于正数数组。一般情况下,输入数组应该通过过滤掉所有非正数来进行预处理。
时间复杂度为 O(N log N)。空间复杂度为 O(N)。
关于arrays - 使用芬威克树或 BIT 的数组中非递减子序列的最大总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15193469/