Рубрики

Самый длинный увеличивающийся размер подпоследовательности (N log N)

Дан массив случайных чисел. Найти самую длинную возрастающую подпоследовательность (LIS) в массиве. Я знаю, что многие из вас, возможно, читали решения по рекурсивному и динамическому программированию (DP). В сообщениях на форуме есть несколько запросов на O (N log N) algo.

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

Рассмотрим входной массив A = {2, 5, 3}. Я буду расширять массив во время объяснения.

Из наблюдения мы знаем, что LIS является либо {2, 3}, либо {2, 5}. Обратите внимание, что я рассматриваю только строго возрастающие последовательности .

Давайте добавим еще два элемента, скажем, 7, 11 в массив. Эти элементы будут расширять существующие последовательности. Теперь возрастающими последовательностями являются {2, 3, 7, 11} и {2, 5, 7, 11} для входного массива {2, 5, 3, 7, 11}.

Далее, мы добавляем еще один элемент, скажем, 8 к массиву, т. Е. Входной массив становится {2, 5, 3, 7, 11, 8}. Обратите внимание, что последний элемент 8 больше, чем наименьший элемент любой активной последовательности ( будет кратко обсуждаться об активных последовательностях ). Как мы можем расширить существующие последовательности с 8? Прежде всего, может ли 8 быть частью LIS? Если да, то как? Если мы хотим добавить 8, оно должно идти после 7 (заменяя 11).

Поскольку этот подход является автономным (что мы подразумеваем под автономным ?) , Мы не уверены, продлит ли добавление 8 серию или нет. Предположим, что во входном массиве 9, скажем, {2, 5, 3, 7, 11, 8, 7, 9…}. Мы можем заменить 11 на 8, так как есть потенциально лучший кандидат (9), который может расширить новую серию {2, 3, 7, 8} или {2, 5, 7, 8}.

Наше наблюдение состоит в том, предположим, что конечным элементом наибольшей последовательности является E. Мы можем добавить (заменить) текущий элемент A [i] к существующей последовательности, если существует элемент A [j] (j> i) такой, что E <A [i] <A [j] или (E> A [i] <A [j] — для замены). В приведенном выше примере E = 11, A [i] = 8 и A [j] = 9.

В случае нашего исходного массива {2, 5, 3}, обратите внимание, что мы сталкиваемся с той же ситуацией, когда добавляем 3 в возрастающую последовательность {2, 5}. Я просто создал две увеличивающиеся последовательности, чтобы сделать объяснение простым. Вместо двух последовательностей 3 может заменить 5 в последовательности {2, 5}.

Я знаю, что это будет сбивать с толку, я скоро это проясню!

Вопрос в том, когда будет безопасно добавлять или заменять элемент в существующей последовательности?

Рассмотрим другой пример A = {2, 5, 3}. Скажем, следующий элемент равен 1. Как он может расширять текущие последовательности {2, 3} или {2, 5}. Очевидно, что это также не может распространяться. Тем не менее, существует вероятность того, что новый наименьший элемент может быть началом LIS. Чтобы было понятно, рассмотрим массив {2, 5, 3, 1, 2, 3, 4, 5, 6}. Создание 1 как новой последовательности создаст новую последовательность, которая является самой большой.

Наблюдение состоит в том, что, когда мы сталкиваемся с новым наименьшим элементом в массиве, он может быть потенциальным кандидатом для начала новой последовательности.

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

В общем, у нас есть множество активных списков различной длины. Мы добавляем элемент A [i] в эти списки. Мы сканируем списки (для конечных элементов) в порядке убывания их длины. Мы проверим конечные элементы всех списков, чтобы найти список, конечный элемент которого меньше, чем A [i] ( минимальное значение).

Наша стратегия определяется следующими условиями,

1. If A[i] is smallest among all end 
   candidates of active lists, we will start 
   new active list of length 1.
2. If A[i] is largest among all end candidates of 
  active lists, we will clone the largest active 
  list, and extend it by A[i].

3. If A[i] is in between, we will find a list with 
  largest end element that is smaller than A[i]. 
  Clone and extend this list by A[i]. We will discard all
  other lists of same length as that of this modified list.

Обратите внимание, что в любом случае во время построения активных списков соблюдается следующее условие.

«Конечный элемент меньшего списка меньше конечных элементов больших списков» .

Это будет ясно на примере, давайте возьмем пример из вики {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

A[0] = 0. Case 1. There are no active lists, create one.
0.
-----------------------------------------------------------------------------
A[1] = 8. Case 2. Clone and extend.
0.
0, 8.
-----------------------------------------------------------------------------
A[2] = 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
-----------------------------------------------------------------------------
A[3] = 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
-----------------------------------------------------------------------------
A[4] = 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
-----------------------------------------------------------------------------
A[5] = 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
-----------------------------------------------------------------------------
A[6] = 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
-----------------------------------------------------------------------------
A[7] = 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[8] = 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[9] = 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
-----------------------------------------------------------------------------
A[10] = 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
-----------------------------------------------------------------------------
A[11] = 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[12] = 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[13] = 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
-----------------------------------------------------------------------------
A[14] = 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------------------------
A[15] = 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS List
----------------------------------------------------------------------------

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

Алгоритм:

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

Мы будем использовать вспомогательный массив для хранения конечных элементов. Максимальная длина этого массива равна длине ввода. В худшем случае массив делится на N списков первого размера ( обратите внимание, что это не приводит к сложности в худшем случае ). Чтобы отбросить элемент, мы проследим значение ceil A [i] во вспомогательном массиве (снова соблюдаем конечные элементы в вашей грубой работе) и заменим значение ceil на A [i]. Мы расширяем список, добавляя элемент во вспомогательный массив. Мы также поддерживаем счетчик для отслеживания длины вспомогательного массива.

Бонус: Вы частично освоили технику сортировки терпения partially

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

Обновление — 17 июля 2016 года : Довольно впечатляющие отзывы читателей и несколько сайтов, ссылающихся на этот пост, чувствуя себя счастливым, когда моя усердная работа помогает другим. Похоже, что читатели не делают никаких домашних заданий до публикации комментариев. Просьба просмотреть некоторые примеры после прочтения статьи, и, пожалуйста, сделайте свою работу на бумаге (не используйте редактор / компилятор). Просьба помочь себе. Профессия «знать» отличается от реального понимания (без неуважения). Ниже приведен мой личный опыт.

Начальная подготовка контента заняла у меня около 6 часов. Но это был хороший урок. Я закончил исходный код через час. Когда я начал писать контент, чтобы объяснить читателю, я понял, что не понимаю случаев. Взял мою записную книжку (у меня есть привычка хранить записную книжку, чтобы отслеживать мою грубую работу), и через несколько часов я заполнил почти 15 страниц грубой работы. Независимо от содержания, которое вы видите в примере серого цвета, с этих страниц. Весь мыслительный процесс для решения, инициируемый запиской в книге «Введение в алгоритмы Уди Манбера», я настоятельно рекомендую практиковать в книге.

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

Обновление — 5 августа 2016 года :

На следующую ссылку стоит ссылаться после выполнения вашей работы. Я узнал ссылку через мой недавно созданный профиль Disqus . Ссылка имеет объяснение подхода, упомянутого в вики.

http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming

Ниже приведен код для определения длины LIS ( обновлен до кода C ++ 11, нет массивов в стиле C ),

C ++

#include <iostream>
#include <vector>

  
// Двоичный поиск (обратите внимание на границы в вызывающей стороне)

int CeilIndex(std::vector<int>& v, int l, int r, int key)

{

    while (r - l > 1) {

        int m = l + (r - l) / 2;

        if (v[m] >= key)

            r = m;

        else

            l = m;

    }

  

    return r;

}

  

int LongestIncreasingSubsequenceLength(std::vector<int>& v)

{

    if (v.size() == 0)

        return 0;

  

    std::vector<int> tail(v.size(), 0);

    int length = 1; // всегда указывает на пустой слот в хвосте

  

    tail[0] = v[0];

    for (size_t i = 1; i < v.size(); i++) {

  

        // новое наименьшее значение

        if (v[i] < tail[0])

            tail[0] = v[i];

  

        // v [i] расширяет наибольшую подпоследовательность

        else if (v[i] > tail[length - 1])

            tail[length++] = v[i];

  

        // v [i] станет конечным кандидатом существующего

        // подпоследовательность или выбросить более крупные элементы во всех

        // LIS, чтобы освободить место для предстоящих элементов терки

        // чем v [i] (а также, v [i] уже

        // появился в одной из LIS, определил местоположение

        // и замени его)

        else

            tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];

    }

  

    return length;

}

  

int main()

{

    std::vector<int> v{ 2, 5, 3, 7, 11, 8, 10, 13, 6 };

    std::cout << "Length of Longest Increasing Subsequence is "

              << LongestIncreasingSubsequenceLength(v) << '\n';

    return 0;

}

Джава

// Java-программа для поиска длины самой длинной увеличивающейся подпоследовательности
// за O (n Log n) время

import java.io.*;

import java.util.*;

import java.lang.Math;

  

class LIS {

    // Двоичный поиск (обратите внимание на границы в вызывающей стороне)

    // A [] это ceilIndex в вызывающей

    static int CeilIndex(int A[], int l, int r, int key)

    {

        while (r - l > 1) {

            int m = l + (r - l) / 2;

            if (A[m] >= key)

                r = m;

            else

                l = m;

        }

  

        return r;

    }

  

    static int LongestIncreasingSubsequenceLength(int A[], int size)

    {

        // Добавить граничный случай, когда размер массива равен единице

  

        int[] tailTable = new int[size];

        int len; // всегда указывает на пустой слот

  

        tailTable[0] = A[0];

        len = 1;

        for (int i = 1; i < size; i++) {

            if (A[i] < tailTable[0])

                // новое наименьшее значение

                tailTable[0] = A[i];

  

            else if (A[i] > tailTable[len - 1])

                // A [i] хочет расширить наибольшую подпоследовательность

                tailTable[len++] = A[i];

  

            else

                // A [i] хочет быть текущим конечным кандидатом существующего

                // подпоследовательность Он заменит значение ceil в tailTable

                tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];

        }

  

        return len;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };

        int n = A.length;

        System.out.println("Length of Longest Increasing Subsequence is " + LongestIncreasingSubsequenceLength(A, n));

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

python3

# Python программа для поиска
# длина самого длинного
# увеличение подпоследовательности
# за O (n Log n) время

  
# Бинарный поиск (примечание
# границы в звонилке)
# A [] - ceilIndex
# в звонящем

def CeilIndex(A, l, r, key):

  

    while (r - l > 1):

      

        m = l + (r - l)//2

        if (A[m] >= key):

            r = m

        else:

            l = m

    return r

   

def LongestIncreasingSubsequenceLength(A, size):

  

    # Добавить граничный регистр,

    # когда размер массива равен единице

   

    tailTable = [0 for i in range(size + 1)]

    len = 0 # всегда указывает пустой слот

   

    tailTable[0] = A[0]

    len = 1

    for i in range(1, size):

      

        if (A[i] < tailTable[0]):

  

            # новое наименьшее значение

            tailTable[0] = A[i]

   

        elif (A[i] > tailTable[len-1]):

  

            # A [i] хочет продлить

            # наибольшая подпоследовательность

            tailTable[len] = A[i]

            len+= 1

   

        else:

            # A [i] хочет быть текущим

            # конечный кандидат существующего

            # подпоследовательность. Это заменит

            # значение ceil в tailTable

            tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i]

          

   

    return len

  

   
# Драйвер программы для
# проверка над функцией

  

A = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ]

n = len(A)

  

print("Length of Longest Increasing Subsequence is ",

       LongestIncreasingSubsequenceLength(A, n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для определения длины самого длинного
// увеличиваем подпоследовательность в O (n Log n)
// время

using System;

  

class GFG {

  

    // Бинарный поиск (обратите внимание на границы

    // в вызывающей стороне) A [] - ceilIndex

    // в вызывающей

    static int CeilIndex(int[] A, int l,

                         int r, int key)

    {

        while (r - l > 1) {

            int m = l + (r - l) / 2;

  

            if (A[m] >= key)

                r = m;

            else

                l = m;

        }

  

        return r;

    }

  

    static int LongestIncreasingSubsequenceLength(

        int[] A, int size)

    {

  

        // Добавить граничный случай, когда размер массива

        // является одним

  

        int[] tailTable = new int[size];

        int len; // всегда указывает на пустой слот

  

        tailTable[0] = A[0];

        len = 1;

        for (int i = 1; i < size; i++) {

            if (A[i] < tailTable[0])

                // новое наименьшее значение

                tailTable[0] = A[i];

  

            else if (A[i] > tailTable[len - 1])

  

                // A [i] хочет расширить самый большой

                // подпоследовательность

                tailTable[len++] = A[i];

  

            else

  

                // A [i] хочет быть текущим концом

                // кандидат существующего

                // подпоследовательность Это заменит

                // значение ceil в tailTable

                tailTable[CeilIndex(tailTable, -1,

                                    len - 1, A[i])]

                    = A[i];

        }

  

        return len;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        int[] A = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };

        int n = A.Length;

        Console.Write("Length of Longest "

                      + "Increasing Subsequence is " + LongestIncreasingSubsequenceLength(A, n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска
// длина самого длинного
// увеличиваем подпоследовательность
// за O (n Log n) время

  
// Бинарный поиск (примечание
// границы в вызывающей стороне)
// A [] - ceilIndex
// в вызывающей

function CeilIndex($A, $l, $r, $key)

{

    while ($r - $l > 1)

    {

        $m = (int)($l + ($r - $l)/2);

        if ($A[$m] >= $key)

            $r = $m;

        else

            $l = $m;

    }

    return $r;

}

  

function LongestIncreasingSubsequenceLength($A, $size)

{

    // Добавить граничный регистр,

    // когда размер массива равен единице

  

    $tailTable = array_fill(0, ($size + 1), 0);

    $len = 0; // всегда указывает на пустой слот

  

    $tailTable[0] = $A[0];

    $len = 1;

    for($i = 1; $i < $size; $i++)

    {

      

        if ($A[$i] < $tailTable[0])

            // новое наименьшее значение

            $tailTable[0] = $A[$i];

  

        else if ($A[$i] > $tailTable[$len-1])

        {

            // A [i] хочет расширить

            // самая большая подпоследовательность

            $tailTable[$len] = $A[$i];

            $len++;

        }

        else

            // A [i] хочет быть текущим

            // конец кандидата существующего

            // подпоследовательность Это заменит

            // значение ceil в tailTable

            $tailTable[CeilIndex($tailTable, -1, $len-1, $A[$i])] = $A[$i];

          

    }

    return $len;

}

  
// Драйвер программы для
// проверить вышеуказанную функцию

$A = array( 2, 5, 3, 7, 11, 8, 10, 13, 6 );

$n = count($A);

  

print("Length of Longest Increasing Subsequence is ".

        LongestIncreasingSubsequenceLength($A, $n));

  
// Этот код предоставлен chandan_jnu
?>


Выход:

Length of Longest Increasing Subsequence is 6

Сложность:

Цикл работает для N элементов. В худшем случае (что является входным сигналом в худшем случае?), Мы можем закончить запросом значения ceil, используя двоичный поиск (log i ) для многих A [i].

Следовательно, T (n) <O (log N!) = O (N log N). Проанализируйте, чтобы убедиться, что верхняя и нижняя границы также равны O (N log N). Сложность ТЕТА (N log N).

Упражнения:

1. Разработайте алгоритм построения самого длинного увеличивающегося списка . Кроме того, смоделируйте свое решение, используя DAG.

2. Разработайте алгоритм для построения всех увеличивающихся списков одинакового по длине размера .

3. Является ли вышеуказанный алгоритм онлайн алгоритмом?

4. Разработать алгоритм построения самого длинного убывающего списка.


Альтернативная реализация с использованием lower_bound () в C ++ :

#include<bits/stdc++.h>

using namespace std; 

  

int LongestIncreasingSubsequenceLength(std::vector<int>& v) 

    if (v.size() == 0) 

        return 0; 

  

    std::vector<int> tail(v.size(), 0); 

    int length = 1; // всегда указывает на пустой слот в хвосте

  

    tail[0] = v[0]; 

      

    for (int i = 1; i < v.size(); i++) { 

  

            // Выполняем бинарный поиск элемента в

            // диапазон от начала до начала + длина

        auto b = tail.begin(), e = tail.begin() + length;

        auto it = lower_bound(b, e, v[i]); 

              

        // Если нет, заменить элемент tail на v [i]

        if (it == tail.begin() + length)

        tail[length++] = v[i]; 

        else   

        *it = v[i]; 

    

  

    return length; 

  

int main() 

    std::vector<int> v{ 2, 5, 3, 7, 11, 8, 10, 13, 6 }; 

    std::cout << "Length of Longest Increasing Subsequence is "

            << LongestIncreasingSubsequenceLength(v); 

    return 0; 

Выход:

Length of Longest Increasing Subsequence is 6

Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Самый длинный увеличивающийся размер подпоследовательности (N log N)

0.00 (0%) 0 votes