> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/twitter/longest-increasing-subsequence.md).

# 300. Longest increasing subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,\
Given`[10, 9, 2, 5, 3, 7, 101, 18]`,\
The longest increasing subsequence is`[2, 3, 7, 101]`, therefore the length is`4`. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n^2) complexity.

**Follow up:**Could you improve it to O(nlogn) time complexity?

**Credits:**\
Special thanks to[@pbrother](https://leetcode.com/discuss/user/pbrother)for adding this problem and creating all test cases.

**Thoughts**

1. O(n^2) solution with [recursive and dynamic programming approach by GeeksforGeeks](https://www.geeksforgeeks.org/?p=12832)
2. [Dynamic Programming](https://leetcode.com/problems/longest-increasing-subsequence/discuss/74825) (Original [GeeksforGeeks](https://www.geeksforgeeks.org/?p=12832) explanation) **O(n^2)**
3. [Binary search + Dynamic Programming](https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824): **O(nlogn)** (Original [GeeksforGeeks](https://www.gitbook.com/book/ttzztt/lc/edit#) explanation)

**Code Binary Search (Java)** inspired by [GeeksforGeeks](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/): **“end element of smaller list is smaller than end elements of larger lists“.**

```cpp
record the tail table by keeping updating current value to correct position into the tail table 
through binary search
```

```cpp
class Solution {
    public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = 0, j = size;
        while (i != j) {
            int m = (i + j) / 2;
            if (tails[m] < x)
                i = m + 1;
            else
                j = m;
        }
        tails[i] = x;
        if (i == size) ++size;
    }   
    return size;
    }
}
```

using **Arrays.binarySearch** by [jopiko123](https://leetcode.com/jopiko123):

```java
public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}
```

**Code Binary Search** with **O(nlogn)** by [dtccwl](https://leetcode.com/dtccwl), inspired by [GeeksforGeeks](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/)

```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if(it==res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
    }
};
```