# Задача 05 — длиннейшая возрастающая подпоследовательность (C++)

## Глава I. Общая информация

- **Цель:** посчитать длину строго возрастающей подпоследовательности массива за
  O(n log n), а не за наивные O(n²).
- **Почему это в Eltex:** задача — эталон на «знаешь ли ты приём tails + бинарный поиск
  поверх DP», а сам паттерн «поддерживать отсортированный массив минимально возможных хвостов
  и подставлять новый элемент через `lower_bound`» переиспользуется в задачах на планирование
  и в сравнении версий (diff-подобные алгоритмы ищут именно длиннейшие совпадающие/растущие
  подпоследовательности).
- **Что сдаётся:** `solution.cpp`, проходящий `python3 grade.py 05`.

## Глава II. Что нужно знать до старта

Наивное решение — DP: `dp[i]` = длина LIS, заканчивающейся на элементе `i`, пересчитывается
перебором всех `j < i` — O(n²), при 100 000 элементах это ~10¹⁰ операций и тест не пройдёт
(ограничение — 2 секунды).

Быстрое решение — «хвосты» (patience sorting): массив `tails`, где `tails[k]` — минимально
возможный последний элемент возрастающей подпоследовательности длины `k+1`, накопленной по
уже просмотренному префиксу. Массив `tails` всегда отсортирован по построению, поэтому для
каждого нового `x` бинарным поиском (`lower_bound`) находится первая позиция с
`tails[pos] >= x`: если такая позиция есть — `x` заменяет значение в ней (подпоследовательность
той же длины, но с меньшим хвостом — выгоднее для будущих продолжений); если позиции нет —
`x` дописывается в конец, увеличивая длину LIS на 1. Именно `lower_bound`, а не `upper_bound` —
строгое возрастание требует заменить первый элемент `>= x`, а не `> x` (иначе повторяющиеся
значения ошибочно продлевают подпоследовательность).

Итоговая длина `tails` в конце обработки массива и есть `lis_length`. Значения в `tails` —
это не сама LIS, только корректная её длина.

Почему дальше: тот же приём «поддерживай отсортированный инвариант + `lower_bound`» стоит
знать и для задач на минимальное число возрастающих подпоследовательностей на весь массив.

## Глава III. Задание

```c++
int lis_length(const std::vector<int>& a);   // длина НВП (строго возрастающей)
```

Требования:
- пустая последовательность → 0;
- работа за O(n log n); наивное O(n²) не пройдёт проверку на 100 000 элементах
  (внутренний тест меряет время и роняет прогон при > 2 с);
- подпоследовательность не обязана быть непрерывной.

Проверка: `python3 grade.py 05`. Критерий: все `ok`, сборка без предупреждений.

## Глава IV. Ловушки

- `upper_bound` вместо `lower_bound` при строгом возрастании → повторяющиеся значения
  ошибочно продлевают подпоследовательность → длина LIS завышена на массивах с дубликатами
  (например, `[1, 1, 1]` должен дать 1, а не 3).
- Наивная DP-версия за O(n²) → проходит маленькие тесты, но на 100 000 элементах превышает
  лимит в 2 секунды → `grade.py 05` роняет прогон по таймауту, а не по неверному ответу.
- Не обработан пустой вектор отдельным веткой → если код полагается на то, что цикл по
  пустому диапазону сам вернёт 0, это обычно верно, но стоит явно проверить — тихая логическая
  ошибка здесь не кидает исключение, просто даёт неверный ответ на пограничном тесте.

**Факты для карточек**
- base | Сложность наивного DP-решения LIS? — O(n²)
- core | Сложность решения через `tails` + бинарный поиск? — O(n log n)
- core | Что хранит `tails[k]`? — минимально возможный последний элемент возрастающей
  подпоследовательности длины `k+1`
- deep | Почему для строгого возрастания нужен `lower_bound`, а не `upper_bound`? —
  `lower_bound` находит первый элемент `>= x` и заменяет его, не давая повторам продлевать
  подпоследовательность

## После сдачи

Разбор: почему массив `tails` не является самой LIS, а только хранит её длину через
минимальные возможные хвосты; как по `tails` при необходимости восстановить саму
подпоследовательность (дополнительный массив предшественников).