Разбор задачи «Башни сигнала»

Идея задачи

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

Подпоследовательность получается из массива удалением некоторых элементов без изменения порядка оставшихся.

Например, для массива

10 9 2 5 3 7 101 18

одна из возрастающих подпоследовательностей — 2 3 7 18, её длина равна 4.

Именно такой ответ и нужно вывести.

Что здесь важно понять

Многие поначалу путают:

• подмассив — это непрерывный кусок массива;
• подпоследовательность — это элементы, выбранные в исходном порядке, но не обязательно подряд.

В этой задаче нужна именно подпоследовательность.

То есть из массива

3 1 5 2 6

можно взять 3 5 6, можно взять 1 2 6, но нельзя переставлять элементы местами.

Способ 1. Динамическое программирование за O(n^2)

Это самое естественное решение, с которого удобно начинать разбор.

Что будем хранить

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

Тогда ответом будет:

max(dp[i])

Как посчитать dp[i]

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

• j < i
• a[j] < a[i]

Тогда:

dp[i] = max(dp[j] + 1) по всем подходящим j.

Если таких j нет, то элемент a[i] сам образует подпоследовательность длины 1.

Значит:

dp[i] = 1 изначально, а затем пытаемся улучшить.

Переход

Для каждого i:

• ставим dp[i] = 1
• перебираем все j < i
• если a[j] < a[i], то dp[i] = max(dp[i], dp[j] + 1)

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

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

Пример работы DP

Рассмотрим массив:

10 9 2 5 3 7 101 18

Посчитаем dp:

• 10 → dp[0] = 1
• 9 → меньше предыдущего, значит dp[1] = 1
• 2 → тоже 1
• 5 → можно продолжить 2, значит dp[3] = 2
• 3 → можно продолжить 2, значит dp[4] = 2
• 7 → можно продолжить 2, 5 или 2, 3, значит dp[5] = 3
• 101 → можно продолжить лучшую из предыдущих, значит dp[6] = 4
• 18 → можно продолжить подпоследовательность длины 3, значит dp[7] = 4

Итоговый ответ: 4.

Код на C++ — решение за O(n^2)

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

using namespace std;

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

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

    vector<int> dp(n, 1);
    int ans = 1;

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

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

Код на Python — решение за O(n^2)

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

dp = [1] * n
ans = 1

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

print(ans)

Почему этого может быть недостаточно

Если n маленькое, решение за O(n^2) подходит.

Но в этой задаче ограничения большие, например до 2 * 10^5. Тогда двойной цикл уже слишком медленный.

Нужно более быстрое решение — за O(n log n).

Способ 2. Оптимальное решение за O(n log n)

Это классический алгоритм для LIS.

Основная идея

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

Пусть d[len] — минимальный возможный последний элемент строго возрастающей подпоследовательности длины len + 1.

Идея очень важная:

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

То есть нас интересует не сама подпоследовательность, а только лучший «хвост» для каждой длины.

Как обновлять массив d

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

Пусть текущий элемент равен x.

Нужно найти первое место в d, где стоит число не меньше x.

• если такого места нет, значит x больше всех хвостов, и мы можем увеличить длину ответа: добавляем x в конец d;
• иначе заменяем найденный элемент на x.

Для поиска используем бинарный поиск.

Именно поэтому итоговая сложность — O(n log n).

Почему используется именно lower_bound / bisect_left

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

Поэтому ищем первую позицию, где значение >= x.

Это и делает:

• lower_bound в C++
• bisect_left в Python

Если бы задача была про неубывающую подпоследовательность, тогда логика была бы другой.

Пошаговый пример

Массив:

10 9 2 5 3 7 101 18

Шаги

1. 10 → d = [10]
2. 9 → заменяем 10 на 9 → d = [9]
3. 2 → заменяем 9 на 2 → d = [2]
4. 5 → больше последнего → d = [2, 5]
5. 3 → заменяем 5 на 3 → d = [2, 3]
6. 7 → добавляем → d = [2, 3, 7]
7. 101 → добавляем → d = [2, 3, 7, 101]
8. 18 → заменяем 101 на 18 → d = [2, 3, 7, 18]

Ответ — длина массива d, то есть 4.

Очень важное замечание

Массив d не обязан совпадать с какой-то реальной LIS целиком.

Он хранит только лучшие возможные хвосты.

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

Это и есть ключевая идея алгоритма.

Почему алгоритм корректен

Сформулируем интуицию аккуратно.

После обработки некоторого префикса массива:

• для каждой длины L в d[L - 1] хранится минимально возможный хвост возрастающей подпоследовательности длины L;
• если мы уменьшаем хвост, длина подпоследовательности не портится, но возможности продолжения становятся только лучше.

Когда приходит новый элемент x:

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

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

Следовательно, длина d в конце равна ответу.

Код на C++ — оптимальное решение за O(n log n)

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

using namespace std;

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

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

    vector<int> d;

    for (int x : a) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()) {
            d.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << d.size() << '\n';
    return 0;
}

Код на Python — оптимальное решение за O(n log n)

from bisect import bisect_left

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

d = []

for x in a:
    i = bisect_left(d, x)
    if i == len(d):
        d.append(x)
    else:
        d[i] = x

print(len(d))

Сравнение двух подходов

DP за O(n^2)

Плюсы:

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

Минусы:

• не проходит при больших ограничениях.

Решение за O(n log n)

Плюсы:

• проходит большие ограничения;
• является стандартным оптимальным решением.

Минусы:

• идея менее очевидна;
• поначалу может быть сложно понять, почему массив хвостов работает корректно.

Типичные ошибки

1. Путать подпоследовательность и подмассив

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

2. Использовать <= вместо <

Подпоследовательность должна быть строго возрастающей.

Значит переходы делаются только при a[j] < a[i].

3. Неправильно использовать бинарный поиск

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

• lower_bound в C++
• bisect_left в Python

4. Думать, что массив d — это сама LIS

Это не обязательно так. Важна только его длина.

5. Забыть про случай n = 1

Если в массиве один элемент, ответ равен 1.

Какие тесты стоит проверить

Минимальный случай

1
5

Ответ:

1

Все элементы равны

7
7 7 7 7 7 7 7

Ответ:

1

Строго возрастающий массив

5
1 2 3 4 5

Ответ:

5

Строго убывающий массив

5
5 4 3 2 1

Ответ:

1

Смешанный пример

8
10 9 2 5 3 7 101 18

Ответ:

4

Итог

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

Есть два основных подхода:

1. Динамическое программирование за O(n^2) — хорошее учебное решение.
2. Массив минимальных хвостов + бинарный поиск за O(n log n) — оптимальное решение для больших ограничений.

Если задача даётся в учебных целях, полезно сначала понять вариант с dp, а потом уже переходить к более быстрому алгоритму.

Для этой задачи в качестве эталонного решения обычно используют именно вариант за O(n log n).

Эталонное решение на C++

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

using namespace std;

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

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

    vector<int> d;

    for (int x : a) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()) {
            d.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << d.size() << '\n';
    return 0;
}

Эталонное решение на Python

from bisect import bisect_left

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

d = []

for x in a:
    i = bisect_left(d, x)
    if i == len(d):
        d.append(x)
    else:
        d[i] = x

print(len(d))