300.最长递增子序列

解法一：动态规划

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如， [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

进阶：
你可以设计时间复杂度为 O(n^2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

解法一：动态规划
dp[i] 是以第 i 位为结尾的最长子序列长度
j 是从 0 到 i ，依次判断 nums[i] nums[j] 的关系从而得到状态转移方程 ```go func lengthOfLIS(nums []int) int { n := len(nums) dp := make([]int, n) res := 1 for i := 0; i < n ;i++ { // 初始值 dp[i] = 1 } for i := 0; i < n;i++ { for j := 0 ; j < i; j ++ {
```
if nums[i] > nums[j] {
  dp[i] = max(dp[i], dp[j] + 1)
}
```
} res = max(res, dp[i]) } return res }

func max (a, b int) int { if a > b { return a } return b }

<a name="sNmMV"></a>
## 解法二：单调栈 + 二分查找

- 新建栈，以用来保存最长上升子序列
- 原序列遍历，每个元素二分法插入到栈中
   - 这里的二分法是取大于等于该元素的左边界，
      - 存在即覆盖
      - 不存在。那就插入到最后

这里需要注意的是：**栈用保存的是比较小的元素，未必是真实的最长上升子序列，但长度是对的。**

**同样的理论也适用于 **[**300.最长递增子序列**](https://www.yuque.com/tsingwong/nrxuwr/twss8n#jNWAV)
```go
func lengthOfLIS(nums []int) int {
  n := len(nums)
  stack := make([]int, n)
  res := 0
  for i := 0;i<n; i++ {
    tmp := leftBound(stack[:res+1], nums[i])
    stack[tmp] = nums[i]
    if tmp == res {
      res++
    }
  }
  return res
}

func leftBound(nums []int, target int) int {
  left, right := 0, len(nums)-1
    for left <= right {
      mid := left + (right - left) >> 1
      if nums[mid] >= target {
         if mid == 0 || nums[mid -1] < target {
            return mid
         }
         right = mid - 1
      } else {
        left = mid + 1
      }
    }
  return right
}

解法一：动态规划