# 300. Longest Increasing Subsequence

{% embed url="<https://leetcode.com/problems/longest-increasing-subsequence/>" %}

brute force 做的话，最无脑方法就是对每个位置有两个选择取或不取，最后有 2\*\*n 个subsequence要判断，肯定不行。改进一点就是做个类似`backtracking`的判断，当前新进元素大于 subsequence 前值，则可以加入，但 worst case 的复杂度仍然没变。

### Dynamic Programming

其实还是能比较容易地看出是`bottom-up DP`，但状态转换方程比较难想：

$$
dp\[i]=max(dp\[j])+1,∀0≤j\<i
$$

即对每个新进元素`i`，`nums[:i+1]`的LIS肯定是`i`前面某一元素`j`的LIS+1(`dp[j]+1`)，有了转换方程的话就不难写了。

```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if not n: return 0
        
        dp = [0 for _ in range(n)]
        maxL = dp[0] = 1
        
        for i in range(1, n):
            submax = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    submax = max(submax, dp[j])
            dp[i] = submax + 1
            maxL = max(maxL, dp[i])
        return maxL
```

### Binary Search

原来这题最好的解法是二分...需要借助这个特征：

> Increasing subsequence 尾元素大小随着 subsequence 长度递增

比如：

```python
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
```

然后只要遍历`nums`中元素，如果当前元素`x`大于所有的`tail`，则把`x`加进 increasing subsequence，并且 size++，否则，需要找到`i`使得`tails[i-1]<x<=tails[i]`，然后用`x`更新`tails[i]`，这边就是使用 `binary search`。

其实我觉得面试能想出这个解法也不太可能，留个档练练二分搜索吧...

```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = [0 for _ in range(len(nums))]
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) // 2
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            tails[i] = x
            size = max(i + 1, size)
        return size
```
