Как найти длину возрастающей

Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности

Задача

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

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

На пальцах

Есть последовательность:

5, 10, 6, 12, 3, 24, 7, 8

Вот примеры подпоследовательностей:

10, 3, 8
5, 6, 3

А вот примеры возрастающих подпоследовательностей:

5, 6, 7, 8
3, 7, 8

А вот примеры возрастающих подпоследовательностей наибольшей длины:

5, 6, 12, 24
5, 6, 7, 8

Да, максимальных тоже может быть много, нас интересует лишь длина.
Здесь она равна 4.

Теперь когда задача определена, решать мы ее начинаем с (сюрприз!) вычисления чисел Фибоначчи, ибо вычисление их — это самый простой алгоритм, в котором используется “динамическое программирование”. ДП — термин, который лично у меня никаких правильных ассоциаций не вызывает, я бы назвал этот подход так — “Программирование с сохранением промежуточного результата этой же задачи, но меньшей размерности”. Если же посчитать числа Фибоначчи с помощью ДП для вас проще пареной репы — смело переходите к следующей части. Сами числа Фибоначчи не имеют отношения к исходной задаче о подпоследовательностях, я просто хочу показать принцип ДП.

Последовательность Фибоначчи O(n)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

Берем 0, прибавляем 1 — получаем 1.
Берем 1, прибавляем 1 — получаем 2.
Берем 1, прибавляем 2 — получаем, ну вы поняли, 3.

Собственно нахождение n-го элемента этой последовательности и будет нашей задачей. Решение кроется в самом определении этой последовательности. Мы заведем один мутабельный массив, в который будем сохранять промежуточные результаты вычисления чисел Фибоначчи, т.е. те самые n-1 и n-2.

Псевдокод:

int numberForIndex(int index) {

   int[] numbers = [0, 1]; // мутабельный массив, можем добавлять к нему элементы

    for (int i = 2; i < index + 1; i++) {
        numbers[index] = numbers[i - 1] + numbers[i - 2];
    }

    return numbers[index];
}

→ Пример решения на Objective-C

→ Тесты

Вот и всё, в этом массиве numbers вся соль ДП, это своего рода кэш (Caсhe), в который мы складываем предыдущие результаты вычисления этой же задачи, только на меньшей размерности (n-1 и n-2), что дает нам возможность за одно действие найти решение для размерности n.

Этот алгоритм работает за O(n), но использует немного дополнительной памяти — наш массив.

Вернемся к нахождению длины максимальной возрастающей подпоследовательности.

Решение за O( n ^ 2)

Рассмотрим следующую возрастающую подпоследовательность:

5, 6, 12

теперь взглянем на следующее число после последнего элемента в последовательности — это 3.

Может ли оно быть продолжением нашей последовательности? Нет. Оно меньше чем 12.

А 24 ?

Оно да, оно может.

Соответственно длина нашей последовательности равна теперь 3 + 1, а последовательность выглядит так:

5, 6, 12, 24

Вот где переиспользование предыдущих вычислений: мы знаем что у нас есть подпоследовательность 5, 6, 12, которая имеет длину 3 и теперь нам легко добавить к ней 24. Теперь у вас есть ощущение того, что мы можем это использовать, только как?

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

Выглядеть это будет так:

Наша задача — заполнить массив counts правильными значениями. Изначально он заполнен единицами, так как каждый элемент сам по себе является минимальной возрастающей подпоследовательностью.

“Что за загадочные i и j?” — спросите вы. Это индексы итераторов по массиву, которые мы будем использовать. Изменяться они будут с помощью двух циклов, один в другом. i всегда будет меньше чем j.

Сейчас j смотрит на 10 — это наш кандидат в члены последовательностей, которые идут до него. Посмотрим туда, где i, там стоит 5.

10 больше 5 и 1 <= 1, counts[j] <= counts[i]? Да, значит counts[j] = counts[i] + 1, помните наши рассуждения в начале?

Теперь таблица выглядит так.

Смещаем j.

Результат:

Имея перед глазами эту таблицу и понимая какие шаги нужно делать, мы теперь легко можем реализовать это в коде.

int longestIncreasingSubsequenceLength( int numbers[]  ) {

    if (numbers.count == 1) {
        return 1;
    }

   int lengthOfSubsequence[] = Аrray.newArrayOfSize(numbers.count, 1);

    for (int j = 1; j < numbers.count; j++) {
        for (int k = 0; k < j; k++) {
            if (numbers[j] > numbers[k]) {
                if (lengthOfSubsequence[j] <= lengthOfSubsequence[k]) {
                 lengthOfSubsequence[j] = lengthOfSubsequence[k] + 1;
                }
            }
        }
    }

    int maximum = 0;

    for (int length in lengthOfSubsequence) {
        maximum = MAX(maximum, length);
    }

    return maximum;
}

→ Реализация на Objective-C
→ Тесты

Вы не могли не заметить два вложенных цикла в коде, а там где есть два вложенных цикла проходящих по одному массиву, есть и квадратичная сложность O(n^2), что обычно не есть хорошо.

Теперь, если вы билингвал, вы несомненно зададитесь вопросом “Can we do better?”, обычные же смертные спросят “Могу ли я придумать алгоритм, который сделает это за меньшее время?”

Ответ: “да, можете!”

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

Бинарный поиск O(log n)

Бинарный поиск работает только на отсортированных массивах. Например, нам нужно найти позицию числа n в отсортированном массиве:
1, 5, 6, 8, 14, 15, 17, 20, 22

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

Мы ищем позицию числа 8 в этом массиве. С какой стороны от середины массива оно будет находиться? 14 — это число в середине массива. 8 < 14 — следовательно 8 левее 14. Теперь нас больше не интересует правая часть массива, и мы можем ее отбросить и повторять ту же самую операцию вновь и вновь пока не наткнемся на 8. Как видите, нам даже не нужно проходить по всем элементам массива, сложность этого алгоритма < O( n ) и равна O (log n).

Для реализации алгоритма нам понадобятся 3 переменные для индексов: left, middle, right.

Ищем позицию числа 8.

Мы отгадали где находится 8 с трёх нот.

int binarySearch(int list [], int value) {

    if !list.isEmpty {
        int left = list.startIndex
        int right = list.endIndex-1

        while left <= right {

            let middle = left + (right - left)/2

            if list[middle] == value{
                return middle
            }

            if value < list[middle]{
                right = middle - 1
            }
            else{
                left = middle + 1
            }
        }
    }
    return nil
}

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

Теперь мы будем проходить по нашему исходному массиву при этом заполняя новый массив, в котором будет храниться возрастающая подпоследовательность. Еще один плюс этого алгоритма: он находит не только длину максимальной возрастающей подпоследовательности, но и саму подпоследовательность.

Как же двоичный поиск поможет нам в заполнении массива подпоследовательности?

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

Если элемент больше максимального элемента в массиве, добавляем элемент в конец. Это просто.

Если такой элемент уже существует в массиве, ничего особо не меняется. Это тоже просто.

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

Все это запутанно, сейчас будет проще, сведем к рассмотрению 2-х оставшихся случаев.

1. Рассматриваемый элемент последовательности (x) меньше чем наибольший элемент в массиве (Nmax), но больше чем предпоследний.
2. Рассматриваемый элемент меньше какого-то элемента в середине массива.

В случае 1 мы просто можем откинуть Nmax в массиве и поставим на его место x. Так как понятно, что если бы последующие элементы были бы больше чем Nmax, то они будут и больше чем x — соответственно мы не потеряем ни одного элемента.

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

Не расстраивайтесь, если не все стало понятно из этого текстового объяснения, сейчас я покажу все наглядно.

Нам нужны:

1. Исходная последовательность
2. Создаем мутабельный массив, где будем хранить возрастающие элементы для подпоследовательности
3. Создаем мутабельный массив размеров подпоследовательности, в которой рассматриваемый элемент является максимальным.

Результат:

int longestIncreasingSubsequenceLength(int numbers[]) {

    if (numbers.count <= 1) {
        return 1;
    }

    int lis_length = -1;

    int subsequence[];
    int indexes[];

    for (int i = 0; i < numbers.count; ++i) {
        subsequence[i] = INT_MAX;
        subsequence[i] = INT_MAX;
    }

    subsequence[0] = numbers[0];
    indexes[0] = 0;

    for (int i = 1; i < numbers.count; ++i) {
        indexes[i] = ceilIndex(subsequence, 0, i, numbers[i]);

        if (lis_length < indexes[i]) {
            lis_length = indexes[i];
        }
    }

    return lis_length + 1;
}

int ceilIndex(int subsequence[], 
              int startLeft, 
              int startRight,
              int key){

    int mid = 0;
    int left = startLeft;
    int right = startRight;
    int ceilIndex = 0;
    bool ceilIndexFound = false;

    for (mid = (left + right) / 2; left <= right && !ceilIndexFound; mid = (left + right) / 2) {
        if (subsequence[mid] > key) {
            right = mid - 1;
        }
        else if (subsequence[mid] == key) {
            ceilIndex = mid;
            ceilIndexFound = true;
        }
        else if (mid + 1 <= right && subsequence[mid + 1] >= key) {
            subsequence[mid + 1] = key;
            ceilIndex = mid + 1;
            ceilIndexFound = true;
        } else {
            left = mid + 1;
        }
    }

    if (!ceilIndexFound) {
        if (mid == left) {
            subsequence[mid] = key;
            ceilIndex = mid;
        }
        else {
            subsequence[mid + 1] = key;
            ceilIndex = mid + 1;
        }
    }

    return ceilIndex;
}

→ Реализация на Objective-C
→ Тесты

Итоги

Мы с вами сейчас рассмотрели 4 алгоритма разной сложности. Это сложности, с которыми вам приходится встречаться постоянно при анализе алгоритмов:

О( log n ), О( n ), О( n * log n ), О( n ^ 2 )

Эта картинка из вот этой статьи

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

Для лучшего понимания я рекомендую вам закодировать эти проблемы самим на привычном вам языке. А еще было бы здорово, если бы вы запостили ссылку на ваше решение в комментах.

Еще предлагаю подумать над тем как доработать последний алгоритм за O (n * log n ) так чтобы вывести еще и саму наибольшую подпоследовательность. Ответ напишите в комментах.

Всем спасибо за внимание, до новых встреч!

Ссылки:
Вопрос на Stackoverflow.com
Примеры реализации на C++ и Java
Видео с объяснением

Решение за время O(N²)

Построим массив , где — это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом . Массив будем заполнять постепенно — сначала , потом и т.д. Ответом на нашу задачу будет максимум из всех элементов массива .
Заполнение массива будет следующим: если , то искомая последовательность состоит только из числа . Если , то перед числом в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент , но такой, что . Пусть на каком-то шаге нам надо посчитать очередное . Все элементы массива до него уже посчитаны. Значит наше мы можем посчитать следующим образом: при условии, что .

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

Псевдокод алгоритма

vector<int> findLIS(vector<int> a):
   int n = a.size                     //размер исходной последовательности
   int prev[0..n - 1]
   int d[0..n - 1]
 
   for i = 0 to n - 1
       d[i] = 1
       prev[i] = -1
       for j = 0 to i - 1
           if (a[j] < a[i] and d[j] + 1 > d[i])
               d[i] = d[j] + 1
               prev[i] = j
 
   pos = 0                            // индекс последнего элемента НВП
   length = d[0]                      // длина НВП
   for i = 0 to n - 1
       if d[i] > length
           pos = i
           length = d[i]
   
   // восстановление ответа
   vector<int> answer
   while pos != -1
       answer.push_back(a[pos])
       pos = prev[pos]
   reverse(answer)
 
   return answer    

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

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

Для восстановления ответа будем поддерживать заполнение двух массивов: и . В будем хранить индекс элемента, на который заканчивается оптимальная подпоследовательность длины , а в — позицию предыдущего элемента для .

Псевдокод алгоритма

vector<int> findLIS(vector<int> a):
   int n = a.size                     //размер исходной последовательности
   int d[0..n]
   int pos[0..n]
   int prev[0..n - 1]
   length = 0
   
   pos[0] = -1
   d[0] = -INF
   for i = 1 to n
       d[i] = INF
   for i = 0 to n - 1
       j = binary_search(d, a[i])
       if (d[j - 1] < a[i] and a[i] < d[j])
           d[j] = a[i]
           pos[j] = i
           prev[i] = pos[j - 1]
           length = max(length, j)
   
   // восстановление ответа
   vector<int> answer
   p = pos[length]
   while p != -1
       answer.push_back(a[p])
       p = prev[p]
   reverse(answer)
 
   return answer

Ещё одно решение за О(N log N)

Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной^[1].

Само табло представляет из себя расположение различных целых чисел в массиве строк, выровненных по левому краю, где в строке содержится элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент , если он больше либо равен , где — длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент , который больше данного . Поставить элемент вместо . С элементом требуется провести те же действия, что и с , только уже на строке табла.

Пример построения табла на массиве  :

1. Берём элемент . Видим, что , который расположен на первой строке в ячейке с индексом . Увеличиваем и .

2. Берём элемент . Видим, что . Увеличиваем и .

3. Аналогично для элемента .

4. Берём элемент . Так как , то бинарным поиском находим нужную нам позицию , такую, что . В данном случае это
первая позиция. Присваиваем и проделываем такую же операцию, но для строки с индексом .

5. Аналогично для элемента .

6. Аналогично для элемента .

Таким образом, длина наибольшей возрастающей подпоследовательности для массива равна (например, подпоследовательность из элементов ).

См. также

• Задача о наибольшей общей подпоследовательности
• Наибольшая общая возрастающая подпоследовательность
• Задача о наибольшей общей палиндромной подпоследовательности

Примечания

Источники информации

• Википедия — Задача поиска наибольшей увеличивающейся подпоследовательности
• Wikipedia — Longest increasing subsequence
• Дистанционная подготовка — Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)
• MAXimal :: algo :: Длиннейшая возрастающая подпоследовательность за O (N log N)

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

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

Например, самая длинная возрастающая подпоследовательность [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] является [0, 2, 6, 9, 11, 15].

Эта подпоследовательность имеет длину 6; входная последовательность не имеет 7-членных возрастающих подпоследовательностей. Самая длинная возрастающая подпоследовательность в этом примере не уникальна.

Например, [0, 4, 6, 9, 11, 15] или же [0, 4, 6, 9, 13, 15] другие возрастающие подпоследовательности той же длины в той же входной последовательности.
 

Потренируйтесь в этой проблеме

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

1. Включить текущий элемент в ЛИС, если он больше, чем предыдущий элемент в ЛИС, и повторить для остальных элементов.
2. Исключить текущий элемент из LIS и повторить для остальных элементов.

Наконец, верните максимальное значение, которое мы получим, включив или исключив текущий элемент. Базовым случаем рекурсии будет отсутствие элементов. Ниже приведена реализация этой идеи на C++, Java и Python:

Временная сложность приведенного выше решения экспоненциальна и занимает место в стеке вызовов.
 

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

 
Мы также можем решить эту проблему восходящим способом. При подходе «снизу вверх» сначала решайте меньшие подзадачи, а затем решайте из них более крупные подзадачи. Следующий восходящий подход вычисляет L[i], для каждого 0 <= i < n, в котором хранится длина самой длинной возрастающей подпоследовательности подмассива arr[0…i] что заканчивается arr[i]. Вычислять L[i], рассмотрим ЛИС всех меньших значений i (сказать j) уже рассчитано и выбрать максимальное L[j], куда arr[j] меньше, чем текущий элемент arr[i]. У него такое же асимптотическое время выполнения, как и у Memoization, но нет накладных расходов на рекурсию.

Ниже приведена реализация этой идеи на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n²) и требует O(n) дополнительное пространство, где n — размер заданной последовательности.

Как распечатать ЛИС?

Рассмотренные выше методы печатают только длину LIS, но не печатают саму LIS. Чтобы распечатать LIS, мы должны сохранить самую длинную возрастающую подпоследовательность в таблице поиска, а не хранить только длину LIS.

Например, рассмотрим массив arr = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]. Самая длинная возрастающая подпоследовательность подмассива arr[0…i] что заканчивается arr[i] находятся:

LIS[0] — 0
LIS[1] — 0 8
LIS[2] — 0 4
LIS[3] — 0 8 12
LIS[4] — 0 2
LIS[5] — 0 8 10
LIS[6] — 0 4 6
LIS[7] — 0 8 12 14
LIS[8] — 0 1
LIS[9] — 0 4 6 9
LIS[10] — 0 4 5
LIS[11] — 0 4 6 9 13
LIS[12] — 0 2 3
LIS[13] — 0 4 6 9 11
LIS[14] — 0 4 6 7
LIS[15] — 0 4 6 9 13 15

Ниже приведена реализация этой идеи на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n²) и требует O(n²) дополнительное пространство, где n — размер заданной последовательности.

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

Проблема самой длинной возрастающей последовательности

 
Использованная литература:

1. Самая длинная возрастающая подпоследовательность — Википедия.

2. Динамическое программирование #1: самая длинная возрастающая подпоследовательность — YouTube.

 Задача. С клавиатуры вводится набор N целых чисел. Найти наибольшую длину возрастающей подпоследовательности.

Пример

N = 10

10 11 20 3 9 27 100 10 5 4

Наибольшая длина: 4

В этом ряду возрастающих подпоследовательностей две: числа 10 11 20 и 3 9 27 100. Наибольшая длина — 4, четыре числа в подпоследовательности 3 9 27 100.

Как будем решать задачу

Введем N — количество чисел в наборе.

Введем с клавиатуры первое число a и за длину возрастающей подпоследовательности возьмем k = 1. За искомую максимальную длину возьмем m = 1.

Далее в цикле для t от 2 до N:

1. введем число b
2. выполним проверку b>a, если условие истинно, то значение k увеличим на 1 (считаем длину возрастающей подпоследовательности), иначе значением k возьмем за 1 (возрастающая подпоследовательность оборвалась)
3. найдем максимальную длину m
4. значение переменной a перезапишем на значение b

Таблица выполнения алгоритма

Программа решения задачи на языке Паскаль

var a,b,k,m,t,N:integer;

begin

  readln(N);

  read(a); k:=1; m:=1;

  for t:=2 to N do

  begin

    read(b);

    if b>a then k+=1 else k:=1;

    m:=max(k,m); //функция нахождения максимума из двух значений

    a:=b;

  end;

  writeln(‘наибольшая длина возрастающей подпоследовательноси: ‘,m);

end.

Результат запуска программы