가장 긴 증가 하위 시퀀스 (N log N)의 구성

난이도 하드
자주 묻는 질문 아마존 은행 바자 Paytm 삼성
배열 이진 검색 동적 프로그래밍조회수 43

문제 정책

당신은 주어진 정렬 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 값의 값을 늘립니다. 그렇지 않으면 현재 배열 요소 위치를 찾아야합니다. 이를 위해 이진 검색을 사용하고 해당 인덱스를 위치로 가져옵니다. 그리고 lastIndexes [position-1]의 값을 firstIndexes [i]로 업데이트하고 lastIndexes [position]을 i로 업데이트합니다.

순회 후에 배열을 인쇄해야합니다. 이를 위해 우리는 마지막에서 0으로 이동합니다.th 순회 할 때마다 각 인덱스를 firstIndexes [i]로 배치하고 초기화하고 배열의 가능한 각 값을 인쇄합니다.

암호

가장 긴 증가 하위 시퀀스 (N log N)의 생성을위한 C ++ 코드

#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

가장 오래 증가하는 하위 시퀀스 (N log N)의 구성을위한 Java 코드

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"은 배열의 요소 수입니다. 두 개의 임시 배열 firstIndexes 및 lastIndexes를 만들었습니다. 공간의 복잡성은 의 위에).

Translate »