1. Идея

Нужно найти подпоследовательность, в которой элементы идут в том же порядке, что и в массиве, строго возрастают по значению и дают максимальную сумму.

Это очень похоже на задачу о наибольшей возрастающей подпоследовательности, только вместо длины мы максимизируем сумму.

Будем использовать динамическое программирование.

Обозначим dp[i] — максимальная сумма строго возрастающей подпоследовательности, которая обязательно заканчивается в позиции i, то есть последним выбранным элементом является a[i].

Тогда ответом будет максимум среди всех dp[i].

2. Наблюдения

Наблюдение 1

Если подпоследовательность заканчивается в a[i], то перед этим можно взять только такой элемент a[j], где:

• j < i, чтобы сохранить порядок;
• a[j] < a[i], чтобы подпоследовательность оставалась строго возрастающей.

Значит, для каждого i надо перебрать все предыдущие позиции j и попробовать продолжить лучшую подпоследовательность, оканчивающуюся в j.

Наблюдение 2

Подпоследовательность может состоять и из одного элемента a[i].

Поэтому начальное значение для dp[i] — это просто a[i].

Это особенно важно, если числа отрицательные: иногда выгоднее взять один элемент, а не пытаться что-то продолжать.

Наблюдение 3

Ограничение n <= 5000 позволяет решение за O(n^2).

Полный перебор всех пар j < i даст примерно 25 миллионов сравнений в худшем случае, что нормально для таких ограничений.

3. Алгоритм

1. Считываем n и массив a.
2. Создаём массив dp длины n.
3. Для каждой позиции i:
   • сначала считаем, что подпоследовательность состоит только из a[i], то есть dp[i] = a[i];
   • перебираем все j от 0 до i - 1;
   • если a[j] < a[i], то можно поставить a[i] после подпоследовательности, оканчивающейся в j;
   • тогда пробуем улучшить dp[i] значением dp[j] + a[i].
4. Поддерживаем общий максимум среди всех dp[i].
5. Выводим этот максимум.

4. Почему это работает

Докажем, почему переход корректен.

Рассмотрим некоторую позицию i. Нас интересует лучшая строго возрастающая подпоследовательность, которая заканчивается именно элементом a[i].

Есть два варианта:

1. Подпоследовательность состоит только из a[i]. Тогда её сумма равна a[i].

2. Перед a[i] есть некоторый предыдущий выбранный элемент a[j]. Тогда обязательно:

   • j < i, потому что это подпоследовательность;
   • a[j] < a[i], потому что она строго возрастающая.

Если последний элемент перед a[i] находится в позиции j, то вся часть подпоследовательности до j должна быть наилучшей возможной среди всех возрастающих подпоследовательностей, заканчивающихся в j. Иначе можно было бы заменить её на более выгодную и получить ещё большую сумму.

Значит, сумма такой подпоследовательности равна dp[j] + a[i].

Остаётся выбрать лучший из всех допустимых j. Поэтому:

• стартуем с dp[i] = a[i];
• для всех j < i, где a[j] < a[i], берём максимум из dp[i] и dp[j] + a[i].

Так мы действительно находим максимальную сумму возрастающей подпоследовательности, заканчивающейся в i.

Так как любая искомая подпоследовательность заканчивается в некоторой позиции массива, общий ответ равен максимуму по всем dp[i].

5. Сложность

Для каждого i перебираются все j < i.

Итоговая сложность:

• по времени: O(n^2)
• по памяти: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<long long> dp(n);
    long long answer = a[0];

    for (int i = 0; i < n; i++) {
        dp[i] = a[i];
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + a[i]);
            }
        }
        answer = max(answer, dp[i]);
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

dp = [0] * n
answer = a[0]

for i in range(n):
    dp[i] = a[i]
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + a[i])
    if dp[i] > answer:
        answer = dp[i]

print(answer)