# 在线性时间内找到大小为3的排序子序列

## 使用案列

`arr[] = {11,34,2,5,1,7,4 }`
`2 5 7`

2小于5，5小于7，因此它们的索引彼此小于。

## 算法

```1. Declare a new array “small” and “great” of size as same as the original array.
2. Set the value of maximum to n-1, and the value of minimum to 0.
3. Marked the first element of the array we created to -1.
4. Traverse the array from i=1 to less than n(n is the length of the array).
1. Check if arr[i] is smaller or equal to arr[minimum], if true
1. Set minimum to i and small[i] to -1.
2. Else put small[i] = minimum.
5. Traverse the array from i=n-2 to less than equal to 0(n is the length of the array).
1. Check if arr[i] is greater than or equal to arr[maximum], if true
1. Set maximum to i and great[i] to -1.
2. Else put great[i] = maximum.
6. Traverse the array from i=0 to n and check if small[i] and great[i] is not equal to -1, then print the arr[small[i]] , arr[i] and arr[great[i]].
1. Return```

## 代码

### C ++代码在线性时间中找到大小为3的排序子序列

```#include<iostream>
using namespace std;

void getTriplet(int arr[], int n)
{
int maximum = n - 1;
int minimum = 0;
int i;

int* small = new int[n];

small[0] = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[minimum])
{
minimum = i;
small[i] = -1;
}
else
small[i] = minimum;
}

int* great = new int[n];

great[n - 1] = -1;
for (i = n - 2; i >= 0; i--)
{
if (arr[i] >= arr[maximum])
{
maximum = i;
great[i] = -1;
}
else
great[i] = maximum;
}

for (i = 0; i < n; i++)
{
if (small[i] != -1 && great[i] != -1)
{
cout << arr[small[i]] << " " << arr[i] << " "<< arr[great[i]];
return;
}
}

delete[] small;
delete[] great;

return;
}
int main()
{
int arr[] = { 11,34,2,5,1,7,4 };
int n = sizeof(arr) / sizeof(arr[0]);
getTriplet(arr, n);
return 0;
}
```
`2 5 7`

### Java代码以线性时间查找大小为3的排序子序列

```class SortedSubsequenceSize3
{
public static void getTriplet(int arr[])
{
int n = arr.length;
int maximum = n - 1;

int minimum = 0;
int i;

int[] small = new int[n];

small[0] = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[minimum])
{
minimum = i;
small[i] = -1;
}
else
small[i] = minimum;
}
int[] great = new int[n];

great[n - 1] = -1;
for (i = n - 2; i >= 0; i--)
{
if (arr[i] >= arr[maximum])
{
maximum = i;
great[i] = -1;
}
else
great[i] = maximum;
}
for (i = 0; i < n; i++)
{
if (small[i] != -1 && great[i] != -1)
{
System.out.println(arr[small[i]] + " " + arr[i] + " " + arr[great[i]]);
return;
}
}
return;
}
public static void main(String[] args)
{
int arr[] = { 11,34,2,5,1,7,4 };
getTriplet(arr);
}
}
```
`2 5 7`

## 复杂度分析

### 时间复杂度

O（N） 哪里 “ n” 是数组中元素的数量。 我们遍历了所有的数组元素。 并且因为数组的大小为N。时间复杂度也是线性的。

### 空间复杂度

O（N） 哪里 “ n” 是数组中元素的数量。 我们一直在为每个数组元素存储较小和较大的元素。 因此，空间复杂度也是线性的。