這篇文章給大家分享的是有關leetcode如何獲取最長遞增子序列的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
給定一個未排序的整數數組，找到最長遞增子序列的個數。
示例 1:
輸入: [1,3,5,4,7]
輸出: 2
解釋: 有兩個最長遞增子序列，分別是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
輸入: [2,2,2,2,2]
輸出: 5
解釋: 最長遞增子序列的長度是1，并且存在5個子序列的長度為1，因此輸出5。
注意: 給定的數組長度不超過 2000 并且結果一定是32位有符號整數。
1，定義l[i]存儲，以nums[i]結尾的最長遞增子序列長度，c[i]為個數
2，則初始化條件為：l[0:len(nums)]=1 c[0:len(nums)=1]
3,對于任意j<i,如果nums[j]<nums[i](注意嚴格遞增)，則l[i]=max(l[i],l[j]+1)
4,如果nums[j]<nums[i] 且l[i]==l[j+1] 則c[i]=c[i]+1
5,找出l[i]==max(l[i]),的下標，把對應c值個數加起來就是答案（補充nums[i]==nums[j]的情況）
func findNumberOfLIS(nums []int) int { if len(nums) < 1 { return 0 } l := make([]int, len(nums)) c := make([]int, len(nums)) max := 0 for i := 0; i < len(nums); i++ { l[i] = 1 c[i] = 1 } for i := 1; i < len(nums); i++ { for j := 0; j < i; j++ { if nums[j] < nums[i] { if l[i] < l[j]+1 { l[i] = l[j] + 1 c[i] = c[j] } else if l[i] == l[j]+1 { c[i] = c[j] + 1 } } } if max < l[i] { max = l[i] } } sum := 0 for i := 0; i < len(nums); i++ { if l[i] == max { sum += c[i] } } return sum}
感謝各位的閱讀！關于“leetcode如何獲取最長遞增子序列”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
