• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

最长递增(严格递增)子序列-可以不连续

开发技术 开发技术 2周前 (04-09) 10次浏览

最长递增(严格递增)子序列-可以不连续

  • 动态规划+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)
}

程序员灯塔
转载请注明原文链接:最长递增(严格递增)子序列-可以不连续
喜欢 (0)