C++: наибольшая возрастающая подпоследовательность

Продолжаю решать задачи на веб-сервисе «CodeRun» от «Яндекса». В этот раз опишу, как решил задачу из группы «легких», которая называется «НВП с восстановлением ответа».

Три поста из шести предыдущих в этой серии постов:

Формулировка задачи

Дана последовательность из N целых чисел. (Число N находится в диапазоне от 1 до 1000, включая границы. Каждое число в последовательности находится в диапазоне от -10’000 до 10’000, включая границы.) Требуется найти наибольшую возрастающую подпоследовательность (НВП) в заданной последовательности чисел.

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

В заданной последовательности могут быть повторяющиеся числа, но в наибольшей возрастающей подпоследовательности не может быть повторяющихся чисел. Это потому, что в НВП подразумевается строгое возрастание, то есть каждое следующее число в подпоследовательности строго больше предыдущего.

Пример ввода данных и вывода результата:

6
3 29 5 5 28 6
3 5 28

Здесь в первой строке ввода задано число N (в данном примере это число 6). Во второй строке ввода заданы члены последовательности, 6 целых чисел. В третьей строке программа вывела результат своей работы — наибольшую возрастающую подпоследовательность (числа 3, 5, 28) для заданной последовательности чисел.

Отмечу, что для заданной последовательности чисел может быть несколько наибольших возрастающих подпоследовательностей. Например, для приведенного примера кроме НВП, которую нашла программа, существует еще НВП в виде чисел 3, 5, 6. Она тоже имеет длину в 3 числа. В таких случаях по условиям задачи можно вывести любую из НВП.

Программа должна уложиться в 1 секунду и использовать не более 64 Мб памяти.

Поиск подхода к решению

Насколько я понял, это одна из классических задач в математике и программировании. В википедии есть страницы, посвященные этой задаче, в том числе на русском и английском языках. На английском языке наибольшую возрастающую подпоследовательность называют «longest increasing subsequence» (LIS). В этих статьях есть объяснение решений и описание алгоритмов — словесное и псевдокодом.

Там описано даже несколько эффективных способов решения этой задачи. Также в интернете есть множество других сайтов, на страницах которых есть объяснение способов решения этой задачи. Кроме этого, разнообразные нейросети (в том числе в поисковых системах) дают описания способов решения этой задачи.

Проблема почти всех этих источников в том, что описание способов решения этой задачи выполняется сложным математическим языком. Вероятно, первые люди, которые занимались решением этой задачи, были математиками. Они написали описание решения для себя, а остальные, похоже, с тех пор тупо передирают написанное ранее. Этим занимаются как разнообразные образовательные сайты, так и нейросети.

В принципе, я не против описания задач и их решений математическим языком. Однако, как и любые другие описания, они бывают удачные и неудачные (сложные для понимания). В данном случае большинство описаний неудачные.

В общем, поскольку псевдокод решений этой задачи доступен повсеместно, то несложно было бы бездумно написать его реализацию на C++ и перейти к следующей задаче. Но мне нравится решать задачи через понимание, а не бездумное перекатывание готовых ответов. Поэтому некоторое время я бился головой о стену, пока не нашел объяснение, которое мне удалось понять. Оно находится на сайте Максима Иванова:

http://e-maxx.ru/algo/longest_increasing_subseq_log

От простого к сложному

На первый взгляд задача кажется элементарной. Но это обманчивое впечатление.

Я быстро написал первую версию программы, которая перебирала в цикле числа заданной последовательности. При этом я считал каждое число последовательности возможным началом НВП (наибольшей возрастающей подпоследовательности). На каждом шаге этого цикла я пытался искать НВП, перебирая следующие числа последовательности и запоминая те, которые больше предыдущего числа.

Постфактум эта идея видится очевидно неправильной, но я хотел начать с чего-то, чтобы вникнуть в задачу поглубже. Например, для приведенного в формулировке задачи примера моя программа выдавала следующее:

6
3 29 5 5 28 6
3 29

Еще эта версия программы находила подпоследовательность чисел 5, 28. Ошибка очевидна: число 29 для первой версии моей программы явилось непреодолимым барьером, потому что следующие числа она уже сравнивала с 29, все они были меньше этого числа и не попадали в вероятную НВП по этой версии программы.

Я не знал, как подойти к решению другими способами. Авторы задачи оставили к задаче метку «dp on sequences». Сокращение «dp» подразумевает «динамическое программирование», с помощью которого я уже решал ранее несколько задач. Максим Иванов советует сначала написать более простую программу, которая находит только длину НВП, без вывода НВП поэлементно. Эту задачу можно решить с помощью динамического программирования. Как только я с этим справился, далее всё пошло, как по маслу.

Словесное описание алгоритма программы, находящей длину НВП:

Получить число N. Получить числа исходной последовательности в вектор numbers.
Создать вектор vp_max_lens из N целых чисел. Каждый элемент вектора инициализировать числом 1. В элементах этого вектора будут сохранены максимальные длины возрастающих подпоследовательностей на промежуточных этапах расчета. Этот вектор будет поэлементно заполняться в цикле далее. Минимальная длина возрастающей подпоследовательности равна 1 (при заданных условиях задачи), поэтому это значение устанавливаю значением по умолчанию.
Запустить цикл расчета из N шагов. На каждом шаге цикла просмотреть заполненные на предыдущих шагах элементы вектора vp_max_lens в связке с элементами вектора numbers. При этом выделить из просматриваемых элементов вектора vp_max_lens элементы с длинами возрастающих последовательностей, которые можно продолжить на текущем шаге цикла (для этого сравнить текущий элемент из вектора numbers с соответствующими предыдущими элементами вектора numbers, текущий элемент должен быть строго больше того, с которым он сравнивается). Из выделенных тут элементов выбрать элемент вектора vp_max_lens с максимальным значением, прибавить к этому значению 1 и запомнить полученный результат в текущем элементе вектора vp_max_lens.
После окончания цикла найти в векторе vp_max_lens максимальное значение и вывести его в консоль. Это и будет длина НВП.

Сам алгоритм и программа довольно простые, но сложно их понятно описать. У меня тут получилось не очень понятно. Попробуем еще разобрать этот алгоритм по шагам на примере из формулировки задачи:

Шаг	Промежуточные НВП	Просматриваемая часть векторов
1	3	3 1	`numbers` `vp_max_lens`
2	3 3, 29	3, 29 1, 2	`numbers` `vp_max_lens`
3	3 3, 29 3, 5	3, 29, 5 1, 2, 2	`numbers` `vp_max_lens`
4	3 3, 29 3, 5 3, 5	3, 29, 5, 5 1, 2, 2, 2	`numbers` `vp_max_lens`
5	3 3, 29 3, 5 3, 5 3, 5, 28	3, 29, 5, 5, 28 1, 2, 2, 2, 3	`numbers` `vp_max_lens`
6	3 3, 29 3, 5 3, 5 3, 5, 28 3, 5, 6	3, 29, 5, 5, 28, 6 1, 2, 2, 2, 3, 3	`numbers` `vp_max_lens`

Видно, что на каждом шаге просматриваемая часть векторов увеличивается, а значит, на каждый следующий шаг требуется больше времени. Информация из колонки «Промежуточные НВП» по рассматриваемому алгоритму нигде не хранится, я ее расписал для наглядности. Нужно понимать, что на больших исходных последовательностях длина НВП не всегда будет оказываться в конце вектора vp_max_lens. Поэтому после окончания цикла поиск максимального значения в векторе vp_max_lens необходим.

Эта табличка с расчетами дает некоторое представление о том, как работает принцип динамического программирования: результаты расчетов, выполненных на текущем шаге цикла, будут использованы на следующем шаге цикла. Из результатов расчетов, полученных на последнем шаге цикла, в итоге можно получить решение задачи в целом.

Эта табличка всё еще не дает понимания, что происходит на каждом шаге. Разберем, к примеру, что происходит на шаге 5. Текущее число в векторе numbers — это 28. Сравниваем число 28 с каждым из предыдущих чисел в векторе numbers и обращаем внимание только на те из них, которые строго меньше числа 28. Это числа 3, 5 и вторая 5. Из этих трех вариантов нужно выбрать вариант с наибольшим соответствующим ему числом из вектора vp_max_lens. То есть можно выбрать любую из двух 5, им обеим в векторе vp_max_lens соответствует длина 2. Теперь к найденной длине 2 добавим единицу и сохраним в векторе vp_max_lens в элементе, соответствующем текущему числу 28 в векторе numbers.

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

Восстановление НВП поэлементно

Вышеописанный алгоритм позволяет найти только длину НВП, а у нас задача — найти не длину НВП, а саму НВП поэлементно. Для этого в алгоритм нахождения длины НВП внесем дополнения.

Для того, чтобы после цикла расчета можно было восстановить НВП поэлементно, предлагается до цикла создать еще один вектор, в котором будем запоминать индексы элементов-родителей текущих элементов в векторе numbers. Под словами «родитель» и «потомок» тут понимаются элементы-члены НВП. Вектор индексов родителей я назвал parents. Его длина тоже равна N. Элементы вектора parents инициализирую числом -1. Это число означает отсутствие родителя. Перед циклом расчета родители элементов вектора numbers пока неизвестны, поэтому все элементы вектора parents пока что равны числу -1.

В цикле расчета на каждом шаге если происходит продление промежуточной НВП, запоминаем в текущий элемент вектора parents индекс элемента в векторе numbers, из которого продлилась промежуточная НВП.

После цикла расчета у нас есть вектор parents, а также мы находим в векторе vp_max_lens элемент с максимальным значением и запоминаем его индекс в переменной ind_max. Этот же индекс является индексом последнего элемента НВП в векторе numbers. Оттолкнувшись от этого последнего элемента НВП, используя данные вектора parents, восстановим НВП поэлементно и запишем ее в вектор nvp.

Поскольку мы восстанавливали НВП поэлементно с конца к началу, то в векторе nvp последовательность получилась в обратном порядке. Можно просто вывести вектор nvp в консоль в обратном порядке и получится искомая НВП поэлементно.

Моя реализация решения на C++

#include <iostream>
#include <vector>   // для std::vector

int main()
{
    // получить количество чисел в последовательности, [1..1000]
    int N{};
    std::cin >> N;
    // получить числа последовательности, каждое в диапазоне [-10'000..10'000]
    std::vector<int> numbers(N);
    for (int n{}; n < N; n++)
        std::cin >> numbers[n];

    std::vector<int> vp_max_lens(N, 1); // длины промежуточных НВП
    std::vector<int> parents(N, -1);    // индексы родителей в numbers

    // расчет длин промежуточных НВП
    for (int n{}; n < N; n++)
    {
        // найти среди промежуточных длин НВП, найденных на предыдущих шагах,
        // те, которые могут продолжиться на текущем шаге; выбрать среди них
        // максимальную длину, прибавить к ней 1 и запомнить
        for (int i{}; i < n ; i++)
        {
            if (numbers[i] < numbers[n] && vp_max_lens[i] + 1 > vp_max_lens[n])
            {
                vp_max_lens[n] = vp_max_lens[i] + 1;
                // дополнительно запомнить индекс предыдущего элемента НВП
                parents[n] = i;
            }
        }
    }

    // найти индекс максимума в vp_max_lens (индекс элемента с длиной НВП)
    int ind_max{};
    for (int i{ 1 }; i < N; i++)
        if (vp_max_lens[i] > vp_max_lens[ind_max]) ind_max = i;
    // отталкиваясь от этого индекса, восстановить НВП поэлементно
    std::vector<int> nvp;
    for (int i{ ind_max }; i > -1; i = parents[i])
        nvp.push_back(numbers[i]);
    // поскольку восстановили НВП поэлементно в обратном порядке,
    // инвертировать при выводе в консоль
    for (int i = nvp.size() - 1; i >= 0; i--)
        std::cout << nvp[i] << ((i != 0) ? ' ': '\n');

    return 0;
}

Проблем с заданным ограничением по времени при решении этой задачи не возникло. Эта реализация успешно прошла автоматическую проверку на веб-сервисе «CodeRun» от «Яндекса».