> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/longest-increasing-subsequence.md).

# Longest Increasing Subsequence

<https://leetcode.com/problems/longest-increasing-subsequence/description/>

> 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(n2) complexity.
>
> Follow up: Could you improve it to O(n log n) time complexity?

## Thoughts

O(N^2)的DP解法参见DP章节, 这里讲二分法。

虽然也要维护一个数组, 但这次的数组的意义和DP解法的意义并不一样, 不要搞混了。\
我们要维护一个tails数组, tails\[i]意味着长度为i的LIS的最小结尾是多少.\
用一下\[<https://leetcode.com/problems/longest-increasing-subsequence/discuss/]的例子>:

> len = 1 : \[4], \[5], \[6], \[3] => tails\[0] = 3\
> len = 2 : \[4, 5], \[5, 6] => tails\[1] = 5\
> len = 3 : \[4, 5, 6] => tails\[2] = 6

长度为1的LIS中尾巴最小的是3, 长度为2的尾巴最小是5...这个数组的值一定是递增的, 用反证法证明, 假如tails\[i] < tails\[i - 1], 也就是长度为i的LIS有一末尾a比长度为i-1的LIS 的尾巴b小, 那么长度为i-1的LIS应该选择a作为最小, 与假设不符.

既然tails是递增数组, 那么我们就可以上二分法了, 遍历nums, 对nums\[i]找在tails中第一个比它大的数, 如果存在就替换它, 不存在就把tails\[i] = num\[i].\
比如nums 之前为\[4, 5, 6, 3], 现在nums\[i] = 4, tails = \[3, 5, 6], 那我们用二分法把5替换成4, 得到\[3, 4, 6]. 意味着长度为2的LIS现在最小的尾巴是4. 这么做的正确性其实不难看出. 因为4比3大, 也就是长度为1的LIS \[3]可以和4形成一个长度为2的LIS\[3, 4]. 而原来长度为2的LIS\[4, 5] 由于4比5小5就被替换下去了. 最后tails的实际长度能扩张到哪, 则意味着LIS最长能有多长. 由此可见, tails 本身并不一定是对于nums的LIS, 如果问题是不光要返回长度, 还要返回具体的LIS, 是 **不能** 直接返回tails的.

## Code

```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int num : nums) {
            auto pos = lower_bound(tails.begin(), tails.end(), num);
            if ((pos - tails.begin()) < tails.size()) {
                *pos = num;
            } else {
                tails.push_back(num);
            }
        }

        return tails.size();
    }
};
```

## Analysis

时间复杂度O(NlgN). 空间O(N).