Рубрики

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

Учитывая массив случайных чисел, найдите самую длинную монотонно возрастающую подпоследовательность (LIS) в массиве.

Если вы хотите понять подход O (NlogN), это очень четко объясняется здесь .

В этом посте обсуждается простая и экономящая время реализация подхода O (NlogN) с использованием stl. Ниже приведен код для LIS O (NlogN):

// Простая реализация C ++ для поиска LIS
#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

  
// Возвращаем длину LIS в arr [] размера N

int lis(int arr[], int N)

{

    int i;

    set<int> s;

    set<int>::iterator k;

    for (i=0; i<N; i++)

    {

        // Проверяем, был ли элемент действительно вставлен

        // Элемент в наборе не вставляется, если он

        // уже присутствует. Посмотри пожалуйста

        // https://www.geeksforgeeks.org/set-insert-function-in-c-stl/amp/

        if (s.insert(arr[i]).second)

        {

            // Находим позицию вставленного элемента в итераторе k

            k = s.find(arr[i]);

  

            k++;  // Найти следующий больший элемент в наборе

  

            // Если новый элемент не вставлен в конец, то

            // удаляем больший элемент рядом с ним (это сложно)

            if (k!=s.end()) s.erase(k);

        }

    }

  

    // Обратите внимание, что набор s может не содержать фактическую LIS, но его размер дает

    // нам длина LIS

    return s.size();

}

  

int main()

{

    int arr[] = {8, 9, 12, 10, 11};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << lis(arr, n)<< endl;

}

Выход:

4

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

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

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

0.00 (0%) 0 votes