最长递增（严格递增）子序列-可以不连续

• 动态规划+sort.SearchInts()

func lengthOfLIS(nums []int) int {
	dp := []int{}
	for _, num := range nums {
		i := sort.SearchInts(dp, num) //min_index
		if i == len(dp) {
			dp = append(dp, num)// num比dp中的元素都大，应加到末尾
		} else {
			dp[i] = num//num应加到dp[i]处
		}
	}
	return len(dp)
}

• 动态规划+二分法

func lengthOfLIS(nums []int) int {
	dp := []int{}
	for _, v := range nums {
		// 如果v比dp的最后一个元素大，说明v放进dp后还是符合严格递增的
		if len(dp)==0 || v>dp[len(dp)-1] {
			dp = append(dp, v)
		} else {
			var left = 0
			var right = len(dp)
			for left < right {
				mid := left + (right-left) / 2
				if dp[mid] < v {
					left = mid + 1
				} else {
					right = mid
				}
			}
			// 此时left==right，写哪个都可以,v就插在此处
			dp[left] = v
		}
	}
	
	return len(dp)
}