最長遞增子序列的構造（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].```

推薦碼

構造最長遞增子序列的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”是數組中元素的數量。 由於我們創建了兩個臨時數組firstIndexes和lastIndexes。 空間複雜度變為 上）.