溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
