300. 最长递增子序列.md

300. 最长递增子序列

题目传送门

点击这里

解题思路

经典的动态规划入门题了，不少人被这道题劝退，但理解了动态规划的三要素，dp数组、状态转移方程、初始化就会很好做。但这道题要结合二分查找来定位更新。具体思路见代码。

代码

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	dp := []int{}
	//dp = append(dp, nums[0])
	for _, v := range nums{
		//如果当前位置的nums[i]大于当前最长长度处的末尾值，那么dp就可以变长1位了。
		if len(dp) == 0 || v > dp[len(dp)-1] {
			dp = append(dp, v)
		}else {
			//如果小于，就去找介于dp[j-1]和dp[j]之间的j，然后更新dp[j],如果没找到的话那就是最后一个值。
			l, r := 0, len(dp)-1
			j := len(dp)-1
			for l <= r {
				mid := (l+r)>>1
				if dp[mid] >= v {
					r = mid - 1
					j = mid
				}else {
					l = mid + 1
				}
			}
			dp[j] = v
		}
	}
	return len(dp)
}