Підпослідовність із максимальною сумою#11653

Підпослідовність із максимальною сумою

1 секунда
128 мегабайтів
Середня

Задано послідовність a_1, a_2, \ldots, a_n довжини . Знайдіть таку її підпослідовність a_{i_1}, a_{i_2}, \ldots, a_{i_k}, що

Вхідні дані

Перший рядок містить довжину послідовності (n \le 10^4). Другий рядок містить цілих чисел a_i (0 \le a_i \le 10^5).

Вихідні дані

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

Приклади

Наприклад, для послідовності \{3, 2, 100, 4, 5, 6\} відповідь 103 = 3 + 100.

Приклад 1

Loading
Loading