Построение самой длинной возрастающей подпоследовательности (N log N)


Сложный уровень Жесткий
Часто спрашивают в Амазонка BankBazaar Paytm Samsung
массив Бинарный поиск Динамическое программирование

Постановка задачи

Вам дается массив of целые. Задача «Построение самой длинной возрастающей подпоследовательности (N log N)» просит построить самую длинную возрастающую подпоследовательность.

Пример

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

объяснение

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

Построение самой длинной возрастающей подпоследовательности (N log N)

Алгоритм построения самой длинной возрастающей подпоследовательности (N log N)

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

объяснение

Мы дали массив целых чисел и попросили построить самая длинная возрастающая подпоследовательность. Для этого мы будем использовать два массива lastIndexes и firstIndexes и заполним их значениями 0 и -1 соответственно. Массив firstIndexes будет инициализирован как 1. Потому что он будет хранить значения как позиции как индексы. Мы будем обновлять значения при обходе массива.

Мы собираемся пройти по массиву от 1 до n. Где n - длина массива. При обходе массив lastIndexes будет использоваться как позиция или индекс массива. Мы проверим некоторые условия, которые мы собираемся проверить, меньше ли текущий элемент массива, чем массив lastIndexes [leng-1]. Длина изначально определена как 1, что означает, что по крайней мере у нас будет подпоследовательность длины 1. Поэтому, если вышеупомянутое условие истинно, обновите lastIndexes [0] до 1.

Нам нужно проверить, больше ли arr [i], чем массив lastIndexes [n-1]. Затем обновите оба массива, установите firstIndexes [i] равным последнему значению lastIndexes [n-1] и lastIndexes [leng] равным i и увеличьте значение leng value. В противном случае нам нужно узнать текущую позицию элемента массива. Для этого мы будем использовать бинарный поиск и получить этот индекс в позицию. И обновите значение lastIndexes [position-1] до firstIndexes [i] и lastIndexes [position] до i.

После обхода нам нужно распечатать массив. Для этого будем переходить от последнего к 0th позиционировать и инициализировать каждый индекс значением firstIndexes [i] после каждого обхода и распечатать каждое возможное значение массива.

Код:

Код C ++ для построения самой длинной возрастающей подпоследовательности (N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

Код Java для построения самой длинной возрастающей подпоследовательности (N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

Анализ сложности

Сложность времени

O (п войти п) где «n» - количество элементов в массиве. Поскольку мы использовали двоичный поиск, который дает нам логарифмический коэффициент. Но если бы нам пришлось вызывать двоичный поиск для каждого индекса. Тогда в худшем случае временная сложность будет O (N log N).

Космическая сложность

О (п) где «n» - количество элементов в массиве. Так как мы создали два временных массива firstIndexes и lastIndexes. Космическая сложность становится НА).