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

// Простая реализация 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;

}