Как найти максимальную сумму между элементами возрастающей подпоследовательности?

#cpp #алгоритм

Вот для примера : 96 24 48 27 3 144 75 144 48.  Ответ : 291. Ограничения N <= 10
^ 5 и время 2 секунды.

Ссылка на задачу
    

Ответы

Ответ 1

Общая идея ровно такая же, как и для обычной задачи где нужно максимизировать длину
последовательности. Решается с помощью дерева отрезков или дерева Фенвика. Ссылки на
идеи http://e-maxx.ru/algo/fenwick_tree http://e-maxx.ru/algo/segment_tree .

Нам нужно уметь быстро за (log n) находить ключ меньше данного с максимальным значением.
(Эквивалентно поиску максимума на отрезке).

псевдокод

for (int i=0;i получили противоречие. Следовательно жадный алгоритм корректен.  

Алгоритм : берём текущий элемент C, смотрим все последовательности q1 <= q2 <= qn
<=C , из всех таких выбираем с максимальной суммой q1+q2+...+qn её и пытаемся продолжить
(если таких нет, то начинаем новую последовательность). 

Заметим, что сама последовательность нас не интересует, нам нужно знать только её
последний элемент и сумму членов. 

Построим дерево, ключ - последний элемент, значение - сумма. 

Теперь просто идём по массиву слева направо, находим максимум на отрезке (-inf, C]
(если ничего нет, то полагаем ответ максимум 0). Изменяем значение текущего элемента
на найденный максимум + C. 

Ответ - максимум по всем A[i] из массива.
Сложность O(n log N) времени, O(n) или O(n log n) памяти (зависит от типа дерева).

Код не пишу специально.


Ответ 2

Для каждого элемента нужно хранить максимальную сумму, заканчивающуюся строго в нём.

Нужно как-то для текущего элемента посчитать ответ за логарифм.

Предположу, что сработает помещение минимального последнего числа для данного ответа
в map. Хотя не могу обосновать, что асимптотика будет приемлемой, поскольку придётся
перебирать элементы из map'а в цикле до момента нахождения ответа.