Подпоследовательность с максимальной суммой

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

Задана последовательность $a_{1}, a_{2}, ..., a_{n}$ длины $n$ . Найдите такую ее подпоследовательность $a_{i_{1}}, a_{i_{2}}, ..., a_{i_{k}}$ , что

числа в подпоследовательности отсортированы в строго возрастающем порядке.
сумма чисел подпоследовательности $a_{i_{1}} + a_{i_{2}} + ... + a_{i_{k}}$ наибольшая

Входные данные

Первая строка содержит длину последовательности $n (n \leq 1 0^{4})$ . Вторая строка содержит $n$ целых чисел $a_{i} (0 \leq a_{i} \leq 1 0^{5})$ .

Выведите сумму максимальной подпоследовательности.

Например, для последовательности ${3, 2, 100, 4, 5, 6}$ ответ будет $103 = 3 + 100$ .

Ввод #1

Ответ #1

Отправки 148

Коэффициент принятия 32 %