> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/lis/334-increasing-triplet-subsequence.md).

# 334 Increasing Triplet Subsequence

## 334. [Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/description/)

## 1. Question

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

> Return true if there exists i, j, k such that arr\[i] < arr\[j] < arr\[k] given 0 ≤ i < j < k ≤ n
>
> -1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

**Examples:**\
Given`[1, 2, 3, 4, 5]`,\
return`true`.

Given`[5, 4, 3, 2, 1]`,\
return`false`.

## 2. Implementation

**(1) DP**

思路: 直接用Longest Increasing Subsequence的做法，如果最长的递增子序列长度大于等于3，则return true。如果遍历整个数组后，最长递增子序列都小于3，则返回false

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }

                maxLen = Math.max(maxLen, dp[i]);
                if (maxLen >= 3) {
                    return true;
                }
            }
        }
        return false;
    }
}
```

**(2) Linear Search**

思路: 因为问题只问是否存在长度为3的increasing subsequence，我们可以维护两个变量min1, min2，min1表示当前在数组i的位置上**最小的数**，min2表示当前数组i的位置上**次小的数**，当我们从左向右扫描数组时，如果当前的数num符合min1 < min2 < num，则返回true

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }

        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num <= min1) {
                min1 = num;
            } 
            else if (num <= min2) {
                min2 = num;
            }
            else {
                return true;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n^2), 空间复杂度O(n)

**Linear Search:** 时间复杂度O(n), 空间复杂度O(1)