Наибольшая возрастающая подпоследовательность с максимальной суммой
Дан массив из
n целых чисел. Ваша задача — найти самую длинную возрастающую подпоследовательность в этом массиве. Если таких подпоследовательностей несколько, можно вывести любую из них.Подпоследовательность массива формируется путём удаления некоторых (возможно, ни одного) элементов без изменения порядка оставшихся. Например, если массив , то является подпоследовательностью массива , а — нет, потому что в ней не сохранён исходный порядок элементов.
💡
Возрастающая подпоследовательность массива — это подпоследовательность, в которой элементы идут в строго возрастающем порядке. Например, если массив , то — возрастающая подпоследовательность, а — нет, поскольку элементы не расположены по возрастанию.
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ 1000) — длина массива.Во второй строке записаны
n целых чисел (), которые являются элементами массива.Выходные данные
Программа должна вывести сумму самой длинной возрастающей подпоследовательности с максимальной суммой.
Входные данные | Выходные данные |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Пояснение
- В первом примере самая длинная возрастающая подпоследовательность с максимальной суммой — это .
- Во втором примере это подпоследовательность .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB