Максимальная сумма неубывающей подпоследовательности в массиве с использованием дерева Фенвика или BIT

Question

Как мы можем найти максимальную сумму неубывающей подпоследовательности в массиве, используя дерево Фенвика? Например, у нас есть 1 4 4 2 2 3 3 1, здесь максимальная сумма неубывающей подпоследовательности равна 11 (1 2 2 3 3).

Answer 1

Максимальная сумма может быть найдена с использованием алгоритма динамического программирования. Просканируйте массив и для каждого элемента добавьте его значение к наибольшей сумме подпоследовательности, которая является действительной (подпоследовательность заканчивается значением, не превышающим этот элемент).

Эффективная реализация нуждается в некотором способе быстрого поиска максимального значения в данном поддиапазоне. Для этого может использоваться расширенное двоичное дерево поиска. Дерево Фенвика - это просто эффективная реализация расширенного бинарного дерева поиска. Наиболее распространенное использование дерева Фенвика - найти сумму значений в некотором поддиапазоне. Тривиальная модификация позволяет использовать ее для поиска максимума поддиапазона (это работает, потому что в этом конкретном случае значения в дереве Фенвика никогда не уменьшаются).

Смотрите этот код 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 словарь используется для уменьшения размера дерева Фенвика с наибольшего числа во входном массиве до размера массива. Первый вложенный while находит максимум поддиапазона в дереве Фенвика. Второй вложенный while обновляет дерево Фенвика после обновления одной из сумм.

Этот код работает только для массива положительных чисел. В общем случае входной массив должен быть предварительно обработан путем отфильтровывания всех неположительных чисел.

Временная сложность составляет O(N log N). Пространственная сложность O(N).