1. Идея

Нужно найти длину наибольшей строго возрастающей подпоследовательности.

Подпоследовательность — это не обязательно подряд идущие элементы, но порядок сохраняется.
Например, из последовательности 5 1 6 2 3 4 1 7 можно выбрать 1 2 3 4 7, и это будет строго возрастающая подпоследовательность длины 5.

Прямое динамическое программирование за O(n^2) здесь не подходит, потому что n может быть до 2 * 10^5.

Поэтому нужен более быстрый метод: хранить для каждой возможной длины лучшую "концовку" возрастающей подпоследовательности и обновлять её с помощью бинарного поиска.

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

Будем поддерживать массив tails.

Смысл tails такой:

• tails[0] — минимальное возможное последнее значение возрастающей подпоследовательности длины 1;
• tails[1] — минимальное возможное последнее значение возрастающей подпоследовательности длины 2;
• ...
• tails[k] — минимальное возможное последнее значение возрастающей подпоследовательности длины k + 1.

Почему важно хранить именно минимальный возможный конец?

Потому что чем меньше последний элемент подпоследовательности, тем легче потом продолжить её новыми числами.

Пример

Пусть уже обработана часть массива, и сейчас:

• есть подпоследовательность длины 3, заканчивающаяся на 10;
• и есть другая подпоследовательность длины 3, заканчивающаяся на 7.

Вторая лучше, потому что к ней можно добавить больше будущих элементов.
Значит, для длины 3 достаточно хранить конец 7, а 10 не нужен.

Ещё одно важное свойство:

Массив tails всегда строго возрастает.

Почему?
Если для подпоследовательности большей длины конец был бы не больше, чем для меньшей длины, это противоречило бы строгому возрастанию.

Раз tails отсортирован, по нему можно делать бинарный поиск.

3. Алгоритм

Обрабатываем элементы массива слева направо.

Для каждого числа x:

1. Найдём первую позицию left в массиве tails, где tails[left] >= x.
2. Возможны два случая:
   • такой позиции нет, то есть x больше всех элементов в tails:
     • добавляем x в конец tails;
   • позиция есть:
     • заменяем tails[left] на x.

В конце ответом будет длина массива tails.

Почему ищем именно первую позицию, где tails[pos] >= x

Потому что:

• если x больше всех концов, то им можно продлить самую длинную найденную подпоследовательность;
• иначе x может улучшить подпоследовательность некоторой длины, сделав её конец меньше.

Для строгого возрастания нужен именно поиск первой позиции с >= x, а не с > x.

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

Докажем идею по шагам.

Что означает tails[i]

После обработки некоторого префикса массива значение tails[i] равно минимально возможному последнему элементу строго возрастающей подпоследовательности длины i + 1.

То есть:

• подпоследовательность такой длины точно существует;
• её конец нельзя сделать меньше, чем хранится в tails, среди уже обработанных элементов.

Что происходит при обработке нового числа x

Пусть бинарный поиск нашёл первую позицию pos, где tails[pos] >= x.

Случай 1: такой позиции нет

Тогда x больше любого элемента в tails.

Значит, x можно приписать к концу самой длинной найденной подпоследовательности, и получится подпоследовательность на 1 длиннее.

Поэтому x добавляется в конец tails.

Случай 2: позиция pos есть

Тогда:

• если pos = 0, число x может стать новым минимальным концом подпоследовательности длины 1;
• если pos > 0, то tails[pos - 1] < x, потому что pos — первая позиция с >= x.

Значит, существует возрастающая подпоследовательность длины pos, которую можно продолжить числом x.
Получается подпоследовательность длины pos + 1 с концом x.

При этом старое значение tails[pos] было не меньше x, значит замена на x только улучшает ситуацию: длина остаётся той же, а конец становится меньше или равен.

Почему длина tails равна ответу

• Каждый элемент tails соответствует реально существующей возрастающей подпоследовательности некоторой длины, значит длина tails не больше ответа.
• Если существует возрастающая подпоследовательность длины L, алгоритм обязательно сможет построить массив tails длины хотя бы L, потому что каждый её элемент по очереди либо улучшит существующий конец, либо увеличит длину.

Следовательно, длина tails в точности равна длине наибольшей строго возрастающей подпоследовательности.

5. Сложность

Пусть n — количество монет.

Для каждого из n элементов выполняется бинарный поиск по массиву tails, длина которого не больше n.

• Время: O(n log n)
• Память: O(n)

Это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

    vector<long long> tails;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;

        int left = 0;
        int right = (int)tails.size();

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        if (left == (int)tails.size()) {
            tails.push_back(x);
        } else {
            tails[left] = x;
        }
    }

    cout << tails.size() << "\n";
    return 0;
}

7. Код на Python 3

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

tails = []

for x in a:
    left = 0
    right = len(tails)
    while left < right:
        mid = (left + right) // 2
        if tails[mid] >= x:
            right = mid
        else:
            left = mid + 1

    if left == len(tails):
        tails.append(x)
    else:
        tails[left] = x

print(len(tails))