最長増加部分列の構築(N log N)


難易度 ハード
よく聞かれる Amazon (アマゾン) バンクバザール Paytm サムスン
配列 バイナリ検索 動的計画法

問題文

あなたは与えられます 配列 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].

説明

整数の配列を指定し、 最長増加部分列。 このために、0つの配列lastIndexesとfirstIndexesを使用し、それぞれ1と-1の値を入力します。 firstIndexes配列はXNUMXとして初期化されます。これは、値をインデックスとしての位置として格納するためです。 配列をトラバースしながら値を更新します。

配列を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値の値を増やします。 それ以外の場合は、現在の配列要素の位置を確認する必要があります。 このために、二分探索を使用して、その位置へのインデックスを取得します。 そして、lastIndexes [position-1]の値をfirstIndexes [i]に更新し、lastIndexes [position]の値をiに更新します。

トラバーサルの後、配列を出力する必要があります。 このために、最後から0までトラバースしますth すべてのトラバーサル後に各インデックスを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 log n) ここで、「n」は配列内の要素の数です。 対数係数を与える二分探索を使用したので。 しかし、各インデックスの二分探索を呼び出す必要がある場合。 その場合、最悪の場合、時間計算量はO(N log N)になります。

スペースの複雑さ

O(N) ここで、「n」は配列内の要素の数です。 XNUMXつの一時配列firstIndexesとlastIndexesを作成したので。 スペースの複雑さは オン).