300. 最长递增子序列的长度 👌

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 字节，美团面试
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

//  时间On^2, 空间On
func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    n := len(nums)
    res := 1
    dp := make([]int, n+1)                //以i结尾的数 最大长度の序列
    for i := 0; i < n; i++ {            //比如1-10，现在i=7，j从0-7走一遍
        dp[i] = 1                       //自身一个数，就是一个长度
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {                //==位置i的最长递增子序列长度 等于j 从0~ i-1各个位置的最长升序子序列 + 1的最大值
                dp[i] = max(dp[i], dp[j] + 1)   //有前面比i数小的，就加一位，比如【2，5，6】小于，就在6前面+2个
            }
        }
        res = max(res, dp[i])
    }
    return res
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

优化思路：

我们组成子序列的时候，不仅要让这个序列尽可能的长，而且要让子序列中的上升的时候尽可能的缓慢，[2,3]就比[2,5]上升的缓慢，这样就有机会能拼接出更长的上升子序列。
我们用一个数组来保存当前的最长上升子序列，这个数组是严格递增的。
因为是严格递增的，数组中最后一个值nums[max]就是最大值，如果下次再碰到一个数字n，它比num[max]还要大，那么很明显，这个子序列的长度就要+1，并且将数组n添加到数组的末尾。

//二分查找 时间nlogn，空间On，    == 本质就是插入到比外面数字大的 里面最小的一个
func lengthOfLIS(nums []int) int {
    res := 0                //最终数组的长度
    n := len(nums)
    dp := make([]int, n)    //动态，被插入的数组

    for _, value := range nums {
        left, right := 0, res

        for left < right {
            mid := (left + right) / 2

            if dp[mid] >= value {            //value就是要插入的那个
                right = mid
            } else {
                left = mid + 1
            }
        }
        if left == res {       //left，right都可以，反正不断二分最终相等了
            res++
        }
        dp[left] = value        // 把这张牌放到牌堆顶
    }

    return res                    // 牌堆数就是 LIS ⻓度
}

//差不多的思路，代码更优美
func lengthOfLIS(nums []int) int {
    var list []int

    for _, v := range nums {
        index := findIndex(list, v)

        if index == len(list) {
            list = append(list, v)
        } else {
            list[index] = v
        }
    }
    return len(list)
}


func findIndex(list []int, target int) int {
    for k, v := range list {
        if v >= target {
            return k
        }
    }
    return len(list)
}