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

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

} 

Решение за время 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)

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

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

Постановка задачи[править | править код]

Отметим, подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов , таких что .
Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n в худшем случае^[1].

Родственные алгоритмы[править | править код]

• Задача наибольшей увеличивающейся подпоследовательности схожа с задачей поиска наибольшей общей подпоследовательности, имеющей квадратичное динамическое решение.
• В частном случае, если строка является перестановкой 1..n, задача имеет решение за n log log n^[2] с использованием деревьев ван Эмде Боаса.
• При использовании дерева, построенного для элементов алфавита, возможно решение задачи за O(n log A), где A — мощность алфавита, определяемая заранее. При реализации сбалансированными деревьями, необязательно задавать A наперёд. По очевидным причинам A ограничивается длиной строки.
• Возможно также свести задачу к поиску длиннейшего пути в ориентированном ациклическом графе, задавая рёбра между возрастающими элементами. Хотя подсчёт длиннейшего пути будет занимать линейное время от числа рёбер, в худшем случае оно может быть квадратично от длины строки.

Пример эффективного алгоритма[править | править код]

Приведем алгоритм решения задачи, работающий за O(n log n).

Для строки x будем хранить массивы M и P длины n.
M[i] содержит индекс наименьшего по величине из последних элементов возрастающих подпоследовательностей x_nj длины i, , найденных на данном шаге.
P[i] хранит индекс предшествующего символа для наидлиннейшей возрастающей подпоследовательности, оканчивающейся в i-й позиции.
На каждом шаге будем хранить текущий максимум длины подпоследовательности и соответствующий индекс конечного символа, не забывая поддерживать свойства массивов. Шаг представляет собой переход к следующему элементу строки, для каждого перехода потребуется не более логарифма времени (бинарный поиск по массиву M).

P = array of length N
M = array of length N + 1
L = 0
for i in range 0 to N-1:
  lo = 1
  hi = L
  while lo ≤ hi:
    mid = ceil((lo+hi)/2)
    if X[M[mid]] < X[i]:
      lo = mid+1
    else:
      hi = mid-1
  newL = lo
  P[i] = M[newL-1]
  M[newL] = i
  if newL > L:
    L = newL
S = array of length L
k = M[L]
for i in range L-1 to 0:
  S[i] = X[k]
  k = P[k]
return S

Очевидно, после выполнения алгоритма, L — длина искомой подпоследовательности, сами же элементы можно получить, разворачивая P рекурсивно из элемента index.

Примечания[править | править код]

Ссылки[править | править код]

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