Наибольшая Возрастающая ПодпоследовательностьLongest Increasing Subsequence

Прямая ДП: пусть dp[i] — длина самой длинной возрастающей подпоследовательности, ЗАКАНЧИВАЮЩЕЙСЯ на элементе arr[i] (это важное уточнение — не "среди первых i элементов", а именно оканчивающейся на i-м). Переход: dp[i] = 1 + max(dp[j]) по всем j < i таким, что arr[j] < arr[i]; если такого j нет, dp[i] = 1 (подпоследовательность из одного элемента). Ответ на всю задачу — максимум по всем dp[i]. Перебор всех j < i для каждого i даёт O(n²) в худшем случае. Восстановить саму подпоследовательность можно, храня для каждого i индекс j, на котором был достигнут максимум, и пройдя по этим ссылкам в обратном порядке от индекса с максимальным dp.Direct DP: let dp[i] be the length of the longest increasing subsequence ENDING at element arr[i] (an important detail — not "among the first i elements," but specifically ending at the i-th one). The transition: dp[i] = 1 + max(dp[j]) over all j < i such that arr[j] < arr[i]; if no such j exists, dp[i] = 1 (a subsequence of one element). The answer to the whole problem is the maximum over all dp[i]. Scanning all j < i for each i gives O(n²) in the worst case. The subsequence itself can be reconstructed by storing, for each i, the index j where the maximum was achieved, and following those links backward from the index with the maximum dp.

Быстрый способ (patience sorting / поддержание "хвостов"): вместо dp[i] поддерживается массив tails, где tails[k] — наименьшее возможное значение последнего элемента возрастающей подпоследовательности длины k+1, построенной из уже просмотренных элементов. Ключевое наблюдение: массив tails всегда отсортирован по возрастанию. Для каждого нового элемента x бинарным поиском находится позиция первого элемента tails, который ≥ x (lower_bound, см. 2.2.3): если такой позиции нет — x продолжает самую длинную на данный момент подпоследовательность, добавляется в конец tails; если позиция найдена — x заменяет tails[pos], потому что x меньше текущего значения и потенциально позволит продолжить более длинную подпоследовательность в будущем более эффективно. Длина ответа — это финальная длина массива tails; сами значения tails НЕ являются самой подпоследовательностью (это лишь оптимальные "хвосты" разной длины), но длина корректна.The fast method (patience sorting / maintaining "tails"): instead of dp[i], maintain an array tails, where tails[k] is the smallest possible value for the last element of an increasing subsequence of length k+1 built from elements seen so far. The key observation: the tails array is always sorted in increasing order. For each new element x, binary search finds the position of the first element in tails that is ≥ x (lower_bound, see 2.2.3): if no such position exists, x extends the longest subsequence found so far, appended to the end of tails; if a position is found, x replaces tails[pos], because x is smaller than the current value and could more efficiently allow extending a longer subsequence later. The answer's length is the final length of the tails array; the tails values themselves are NOT the actual subsequence (they're just the optimal "tails" of various lengths), but the length is correct.

// O(n log n): tails всегда отсортирован, lower_bound — бинарный поиск (2.2.3)// O(n log n): tails is always sorted, lower_bound is binary search (2.2.3)
int lisLength(std::vector<int>& arr) {
    std::vector<int> tails;
    for (int x : arr) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);   // продлить самую длинную// extend the longest
        else *it = x;                              // заменить худший хвост той же длины// replace a worse tail of the same length
    }
    return tails.size();
}

Небольшой массив чисел — сначала проигрывается O(n²) ДП: для каждого элемента показаны стрелки ко всем подходящим j < i и выбранный максимум; затем на том же массиве проигрывается O(n log n) способ: массив tails со вставкой/заменой через бинарный поиск на каждом шаге.A small array of numbers — first the O(n²) DP auto-plays: for each element, arrows to every eligible j < i are shown along with the chosen maximum; then, on the same array, the O(n log n) method auto-plays: the tails array with an insert/replace via binary search at each step.