# 在線性時間內找到大小為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” 是數組中元素的數量。 我們一直在為每個數組元素存儲較小和較大的元素。 因此，空間複雜度也是線性的。