# 最长递增子序列的构造（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。 空间复杂度变为 上）.