小编给大家分享一下golang刷leetcode技巧之如何实现最长上升子序列，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
解题思路：
解法1:动态规划
1，用dp[i]标识，i 位置的最大长度
2，状态转移方程为 dp[i]=max(dp[j]+1) ,j>=0 j<i
3,取dp最大值
解法2:二分查找
1，用数组记录最长递增序列
2，如果当前元素比最大值大，则插在后面
2，通过二分查找在递增序列里查找位置
3，注意和普通二分查找的区别，如果但强位置比序列位置p的元素大，那么插入位置不是p而是p+1
4，输出p的长度
代码实现
func lengthOfLIS(nums []int) int { if len(nums)<1{ return 0 } dp:=make([]int,len(nums)) for i:=0;i<len(nums);i++{ dp[i]=1 } max:=1 for i:=1;i<len(nums);i++{ for j:=0;j<i;j++{ if nums[j]<nums[i] && dp[i]<dp[j]+1{ dp[i]=dp[j]+1 } } if dp[i]>max{ max=dp[i] } } fmt.Println(dp) return max}
func lengthOfLIS(nums []int) int { if len(nums)<1{ return 0 } var dp []int dp=append(dp,nums[0]) for i:=1;i<len(nums);i++{ if nums[i]>dp[len(dp)-1]{ dp=append(dp,nums[i]) }else{ l:=0 r:=len(dp)-1 p:=0 for l<=r{ mid:=(l+r)>>1 if nums[i]>dp[mid]{ p=mid+1 l=mid+1 }else{ r=mid-1 } } fmt.Println(dp,l,r,p,i,nums[i]) dp[p]=nums[i] fmt.Println("111",dp,l,r,p,i,nums[i]) } } fmt.Println(dp) return len(dp)}
看完了这篇文章，相信你对“golang刷leetcode技巧之如何实现最长上升子序列”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
