Как найти самую длинную последовательно

Here is my C++ solution of the problem. The solution is simpler than all of the provided here so far, and it is fast: N*log(N) algorithmic time complexity. I submitted the solution at leetcode, it runs 4 ms, faster than 100% of C++ solutions submitted.

The idea is (in my opinion) clear: traverse the given array of numbers from left to right. Maintain additionally array of numbers (seq in my code), that holds increasing subsequence. When the taken number is bigger than all numbers that the subsequence holds, put it at the end of seq and increase the subsequence length counter by 1. When the number is smaller than the biggest number in the subsequence so far, put it anyway in seq, in the place where it belongs to keep the subsequence sorted by replacing some existing number. The subsequence is initialized with the length of the original numbers array and with initial value -inf, what means smallest int in the given OS.

Example:

numbers = { 10, 9, 2, 5, 3, 7, 101, 18 }

seq = {-inf, -inf, -inf, -inf, -inf, -inf, -inf}

here is how the sequence changes when we traverse the numbers from left to right:

 seq = {10, -inf, -inf, -inf, -inf, -inf, -inf}
 seq = {9, -inf, -inf, -inf, -inf, -inf, -inf}
 seq = {2, -inf, -inf, -inf, -inf, -inf, -inf}
 seq = {2, 5, -inf, -inf, -inf, -inf, -inf}
 seq = {2, 3, -inf, -inf, -inf, -inf, -inf}
 seq = {2, 3, 7, -inf, -inf, -inf, -inf}
 seq = {2, 3, 7, 101, -inf, -inf, -inf}
 seq = {2, 3, 7, 18, -inf, -inf, -inf}

The longest increasing subsequence for the array has length 4.

Here is the code:

int longestIncreasingSubsequence(const vector<int> &numbers){
    if (numbers.size() < 2)
        return numbers.size();
    vector<int>seq(numbers.size(), numeric_limits<int>::min());
    seq[0] = numbers[0];
    int len = 1;
    vector<int>::iterator end = next(seq.begin());
    for (size_t i = 1; i < numbers.size(); i++) {
        auto pos = std::lower_bound(seq.begin(), end, numbers[i]);
        if (pos == end) {
            *end = numbers[i];
            end = next(end);
            len++;
        }
        else
            *pos = numbers[i];
    }
    return len;
}

Well, so far so good, but how do we know that the algorithm computes the length of the longest (or one of the longest, here may be several subsequences of the same size) subsequence? Here is my proof:

Let’s assume that the algorithm does not computes length of the longest subsequence. Then in the original sequence must exist a number such that the algorithm misses and that would make the subsequence longer. Let’s say, for a subsequence x₁, x₂, …, x_n there exists a number y such that x_k < y < x_k+1, 1 <= k <= n. To contribute to the subsequence y must be located in the original sequence between x_k and x_k+1. But then we have contradiction: when the algorithm traverses original sequence from left to right, every time it meets a number bigger than any number in the current subsequence, it extends the subsequence by 1. By the time algorithm would meet such number y the subsequence would have length k and contain numbers x₁, x₂, …, x_k. Because x_k < y, the algorithm would extend the subsequence by 1 and include y in the subsequence. The same logic applies when y is the smallest number of the subsequence and located to the left of x₁ or when y is the biggest number of the subsequence and located to the right of x_n.
Conclusion: such number y does not exists and the algorithm computes the longest increasing subsequence.
I hope that makes sense.

In the final statement, I would like to mention that the algorithm can be easily generalized to compute longest decreasing subsequence as well, for any data types which elements can be ordered.
The idea is the same, here is the code:

template<typename T, typename cmp = std::less<T>>
size_t longestSubsequence(const vector<T> &elements)
{
    if (elements.size() < 2)
        return elements.size();
    vector<T>seq(elements.size(), T());
    seq[0] = elements[0];
    size_t len = 1;
    auto end = next(seq.begin());
    for (size_t i = 1; i < elements.size(); i++) {
        auto pos = std::lower_bound(seq.begin(), end, elements[i], cmp());
        if (pos == end) {
            *end = elements[i];
            end = next(end);
            len++;
        }
        else
            *pos = elements[i];
    }
    return len;
}

Examples of usage:

int main()
{
    vector<int> nums = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
    size_t l = longestSubsequence<int>(nums); // l == 6 , longest increasing subsequence

    nums = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
    l = longestSubsequence<int, std::greater<int>>(nums); // l == 5, longest decreasing subsequence

    vector<string> vstr = {"b", "a", "d", "bc", "a"};
    l = longestSubsequence<string>(vstr); // l == 2, increasing


    vstr = { "b", "a", "d", "bc", "a" };
    l = longestSubsequence<string, std::greater<string>>(vstr); // l == 3, decreasing

} 

Есть список

[1, 2, 3, 10, 8, 12, 13, 14]

Надо найти самую продолжительную последовательность. Например, для примера выше это

[1, 2, 3, 10]

А для такого списка [12, 11, 10, 8, 7, 1, 2, 3] решением будет

[12, 11, 10, 8, 7, 1]

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

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

Например, рассмотрим массив A[] = [8, 9, 6, 4, 5, 7, 3, 2, 4]. Самая длинная чередующаяся длина подпоследовательности равна 6, а подпоследовательность [8, 9, 6, 7, 3, 4] в качестве (8 < 9 > 6 < 7 > 3 < 4).

Обратите внимание, что самая длинная чередующаяся подпоследовательность не уникальна. Ниже приведены еще несколько подпоследовательностей длины 6:

(8, 9, 6, 7, 2, 4)
(8, 9, 4, 7, 3, 4)
(8, 9, 4, 7, 2, 4)
…
…
And many more…

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

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

 
Мы можем использовать рекурсия Для решения этой проблемы. Идея состоит в том, чтобы поддерживать флаг, указывающий, должен ли следующий элемент в последовательности быть меньше или больше предыдущего элемента. Тогда для любого элемента A[i] по индексу i, у нас есть два варианта:

1. Включите элемент в подпоследовательность.
   • Если флаг верен и A[i-1] < A[i], включают A[i] как следующий высокий в подпоследовательности.
   • Если флаг ложный и A[i-1] > A[i], включают A[i] как следующий низкий в подпоследовательности.

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

2. Исключить элемент из подпоследовательности.

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

Алгоритм может быть реализован следующим образом на C++, Java и Python:

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

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

Временная сложность приведенного выше нисходящего решения равна O(n²) и требует O(n) дополнительное пространство, где n — размер заданной последовательности. Мы даже можем написать восходящую версию вышеупомянутого запомненного решения. В следующем коде показано, как это реализовать на C, Java и Python:

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

 
Также см:

Самая длинная проблема переменного подмассива

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

Задача

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

Вообще, это частный случай задачи нахождения общих элементов 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
Видео с объяснением

Наибольшая общая подпоследовательность Объяснение

Одна из наиболее важных реализаций динамического программирования — поиск самой длинной общей подпоследовательности . Сначала определим некоторые основные термины.

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

Подпоследовательность представляет собой последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка остальных элементов. Допустим, у нас есть строка ABC . Если мы стираем нуль или один или несколько символов из этой строки, мы получаем подпоследовательность этой строки. Таким образом, подпоследовательности строки ABC будут { «A» , «B» , «C» , «AB» , «AC» , «BC» , «ABC» , «» }. Даже если мы удалим все символы, пустая строка также будет подпоследовательностью. Чтобы узнать подпоследовательность, для каждого символа в строке мы имеем два варианта: либо мы берем символ, либо нет. Поэтому, если длина строки равна n , существует 2 ⁿ подпоследовательностей этой строки.

Самая длинная общая подпоследовательность:

Как следует из названия, из всех общих подпоследовательностей между двумя строками самая длинная общая подпоследовательность (LCS) — это та, которая имеет максимальную длину. Например: общие подпоследовательности между «HELLOM» и «HMLD» — это «H» , «HL» , «HM» и т. Д. Здесь «HLL» является самой длинной общей подпоследовательностью, длина которой 3.

Метод грубой силы:

Мы можем сгенерировать все подпоследовательности двух строк с использованием обратного отсчета . Затем мы можем сравнить их, чтобы выяснить общие подпоследовательности. После того, как нам понадобится узнать ту, которая имеет максимальную длину. Мы уже видели, что существует 2 ⁿ подпоследовательностей строки длины n . Потребуются годы, чтобы решить проблему, если наши русские кресты 20-25 .

Метод динамического программирования:

Давайте подходим к нашему методу с примером. Предположим, что мы имеем две строки abcdaf и acbcf . Обозначим их с s1 и s2 . Таким образом, самая длинная общая подпоследовательность этих двух строк будет «abcf» , которая имеет длину 4. Снова напоминаю вам, подпоследовательности не обязательно должны быть непрерывными в строке. Чтобы построить «abcf» , мы игнорировали «da» в s1 и «c» в s2 . Как это узнать, используя динамическое программирование?

Мы начнем с таблицы (2D-массив), содержащей все символы s1 в строке и все символы s2 в столбце. Здесь таблица 0-индексируется, и мы помещаем символы от 1 до и далее. Мы будем перемещать таблицу слева направо для каждой строки. Наша таблица будет выглядеть так:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Здесь каждая строка и столбец представляют длину самой длинной общей подпоследовательности между двумя строками, если мы берем символы этой строки и столбца и добавляем к префиксу перед ним. Например: Таблица [2] [3] представляет длину самой длинной общей подпоследовательности между «ac» и «abc» .

0-й столбец представляет собой пустую подпоследовательность s1 . Точно так же 0-я строка представляет собой пустую подпоследовательность s2 . Если взять пустую подпоследовательность строки и попытаться сопоставить ее с другой строкой, независимо от того, как долго длина второй подстроки, то общая подпоследовательность будет иметь длину 0. Таким образом, мы можем заполнить 0-й ряд и 0-й столбцы нулями. Мы получаем:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Давай начнем. Когда мы заполняем таблицу [1] [1] , мы спрашиваем себя, если бы у нас была строка a и другая строка a и ничего больше, какая будет самая длинная общая подпоследовательность здесь? Длина LCS здесь будет 1. Теперь рассмотрим таблицу [1] [2] . У нас есть строка ab и строка a . Длина LCS будет равна 1. Как вы можете видеть, остальные значения будут также 1 для первой строки, так как он рассматривает только строку a с abcd , abcda , abcdaf . Итак, наша таблица будет выглядеть так:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Для строки 2, которая теперь будет включать c . Для таблицы [2] [1] мы имеем ac с одной стороны, а с другой стороны. Таким образом, длина LCS равна 1. Откуда у нас это 1? С вершины, обозначающей LCS a между двумя подстроками. Итак, мы говорим, что если s1 [2] и s2 [1] не совпадают, то длина LCS будет максимальной длины LCS сверху или слева . Взяв длину LCS сверху, это означает, что мы не берем текущий символ из s2 . Аналогично, взяв длину LCS слева, мы не берем текущий символ из s1 для создания LCS. Мы получаем:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Итак, наша первая формула будет:

if s2[i] is not equal to s1[j]
    Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif

Двигаясь дальше, для таблицы [2] [2] имеем строку ab и ac . Поскольку c и b не являются одинаковыми, мы помещаем максимум сверху или слева здесь. В этом случае это снова 1. После этого для таблицы [2] [3] имеем строку abc и ac . На этот раз текущие значения обеих строк и столбцов совпадают. Теперь длина LCS будет равна максимальной длине LCS до + 1. Как мы получаем максимальную длину LCS до сих пор? Мы проверяем диагональное значение, которое представляет наилучшее совпадение между ab и a . Из этого состояния для текущих значений мы добавили еще один символ к s1 и s2, который оказался одним и тем же. Таким образом, длина LCS, разумеется, возрастет. Мы поместим 1 + 1 = 2 в таблицу [2] [3] . Мы получаем,

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Итак, наша вторая формула будет:

if s2[i] equals to s1[j]
    Table[i][j] = Table[i-1][j-1] + 1
endif

Мы определили оба случая. Используя эти две формулы, мы можем заполнить всю таблицу. После заполнения таблицы это будет выглядеть так:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |  1  |  2  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |  1  |  2  |  3  |  3  |  3  |  3  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |  1  |  2  |  3  |  3  |  3  |  4  |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Длина LCS между s1 и s2 будет равна таблице [5] [6] = 4 . Здесь 5 и 6 — длина s2 и s1 соответственно. Наш псевдокод будет:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Сложность времени для этого алгоритма: O (mn), где m и n обозначает длину каждой строки.

Как узнать самую длинную общую подпоследовательность? Мы начнем с нижнего правого угла. Мы проверим, откуда это значение. Если значение идет по диагонали, то есть, если таблица [i-1] [j-1] равна таблице [i] [j] — 1 , мы нажимаем либо s2 [i], либо s1 [j] (оба одинаковы) и двигаться по диагонали. Если значение идет сверху, это означает, что если таблица [i-1] [j] равна таблице [i] [j] , мы переходим к вершине. Если значение идет слева, это означает, что если таблица [i] [j-1] равна таблице [i] [j] , мы перемещаемся влево. Когда мы достигнем самого левого или верхнего столбца, наш поиск заканчивается. Затем мы выставляем значения из стека и печатаем их. Псевдокод:

Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
     if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
        S.push(s1[j])   //or S.push(s2[i])
        i := i - 1
        j := j - 1
    else if Table[i-1][j] == Table[i][j]
        i := i-1
    else
        j := j-1
    endif
endwhile
while S is not empty
    print(S.pop)
endwhile

Следует отметить: если обе таблицы [i-1] [j] и таблица [i] [j-1] равны таблице [i] [j], а таблица [i-1] [j-1] не является равной таблице [i] [j] — 1 , для этого момента может быть два LCS. Этот псевдокод не рассматривает эту ситуацию. Вам придется решить эту проблему, чтобы найти несколько LCS.

Сложность времени для этого алгоритма: O (max (m, n)) .