차례
문제 정책
당신은 주어진 정렬 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) 생성을위한 알고리즘
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를 만들었습니다. 공간의 복잡성은 의 위에).
