Комбо-стрик

В ритм-игре за каждый уровень тебе начисляют целое число очков. Тренер говорит: «Красивое комбо — это когда ты выбираешь несколько сыгранных уровней *в том же порядке*, и в каждом следующем выбранном уровне очков строго больше, чем в предыдущем».

Найди максимальную длину такого комбо.

Формат ввода

• В первой строке дано целое число n — сколько уровней ты сыграл.
• Во второй строке дано n целых чисел a1, a2, ..., an — очки за уровни по порядку.

Формат вывода Выведи одно целое число — максимальную возможную длину комбо (длину самой длинной строго возрастающей подпоследовательности).

Ограничения

• 2 ≤ n ≤ 2500
• -10^9 ≤ ai ≤ 10^9
• Подпоследовательность должна сохранять порядок элементов (нельзя переставлять уровни).

Пример Ввод:

8
5 1 6 2 3 4 0 7

Вывод:

5

Пояснение: например, можно выбрать уровни с очками 1, 2, 3, 4, 7.

Ключевое наблюдение: если комбо заканчивается на уровне i, то предыдущий выбранный уровень должен быть где-то раньше (j < i) и иметь меньшие очки (a[j] < a[i]). Значит, лучшая цепочка в i получается как «лучшая цепочка в каком-то подходящем j + 1».

Это классическая динамика (DP): храним ответ для каждого конца подпоследовательности и постепенно наращиваем.

План:

• Заведи массив dp, где dp[i] — максимальная длина строго возрастающей подпоследовательности, которая заканчивается в позиции i.
• База: любое одиночное число — уже комбо длины 1, значит сначала dp[i] = 1.
• Для каждого i перебери все предыдущие j от 0 до i-1:
• если a[j] < a[i], то можно продолжить комбо: кандидат dp[j] + 1.
• обнови dp[i] максимумом.
• Ответ — max(dp) по всем позициям (комбо может закончиться где угодно).

Мини-сниппет формулы перехода: dp[i] = max(dp[i], dp[j] + 1) при a[j] < a[i].

Сложность: два вложенных цикла дают O(n^2), при n ≤ 2500 это проходит.

Частая ошибка: перепутать «строго» и «нестрого». Тут нужно именно a[j] < a[i], равные значения продолжать нельзя.