Поиск наибольшей непрерывной суммы субарифмов с различными номерами

Question

В заданном массиве найдите наибольшую непрерывную сумму субамберных чисел с различными номерами. Если в любой подматрице есть как минимум два равных числа, то значения этих чисел равны 0.

Все номера положительные.

Я написал алгоритм грубой силы O (n²), но это определенно слишком медленно. Я попытался смешать его, используя алгоритм Кадане, но он, похоже, не работает.

Answer 1

С помощью сегмента дерева можно получить временную сложность O(n log n).

1. Предположим, что левая граница (назовем его L) из ответа фиксирована. Все, что слева от него, можно игнорировать. Каждый элемент остальной части массива может быть представлен как:
   a) +x, если это первое появление x.
   b) -x если это второе появление x.
   c) 0, если это третье (или более позднее) возникновение x,
   , где x = a[i].
   Тогда ответ является наибольшей суммой субарах для всех подмассивов [L, R], где R >= L.

2. Итак, как это можно эффективно реализовать? Сначала создайте дерево сегментов для диапазона [0, n - 1]. Каждый лист в дереве сегментов содержит префиксную сумму, которая начинается с L и заканчивается на этом листе (0). Заполните его для L = 0 (путем итерации по всему массиву и добавления +x или -x в соответствующее количество в дереве сегментов). Эта часть работает в O(n log n). Еще одно наблюдение: при добавлении L значение изменяется только для не более 3 позиций (потому что первое вхождение для числа a[L] теперь находится в другом положении, но для остальных номеров ничего не изменилось). Каждое обновление в дереве сегментов равно O(log n), поэтому O(log n) требуется время для наращивания L раз. Общая сложность проекта - O(n log n), так как L - прирост: O(n) раз. Не забудьте запросить дерево сегментов, чтобы получить максимальное значение для каждого L и выбрать самый большой в качестве ответа.

Итак, все, что вам нужно, это дерево сегментов, которое поддерживает две операции: добавьте одинаковое число ко всем элементам в заданном диапазоне и получите максимум среди всех элементов. Это хорошо известная проблема, и ее не очень сложно реализовать.