给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
复制代码
示例 2：
输入：nums = [0,1,0,3,2,3]输出：4
复制代码
示例 3：
输入：nums = [7,7,7,7,7,7,7]输出：1
复制代码
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
题解：
func lengthOfLIS(nums []int) int { var solution func([]int) int // 解决方案 var max func(x, y int) int // 取最大值 max = func(x, y int) int { if x > y { return x } return y } solution = func(num []int) int { var dpTable = []int{} // 动态规划 dptable var res int // 最长子串长度 for i := 0; i < len(num); i++ { dpTable = append(dpTable, 1) // 初始化所有dptable 值为1 } for i := 0; i < len(num); i++ { for j := 0; j < i; j++ { // dp[5] 为dp[1~4]中最小的统计值+1 if num[i] > num[j] { dpTable[i] = max(dpTable[i], dpTable[j]+1) } } }
for i := 0; i < len(dpTable); i++ { // 取结果的最大值 res = max(res, dpTable[i]) } return res } return solution(nums)}
复制代码
func lengthOfLIS(nums []int) int { var solution func([]int) int // 解决方案 var max func(x, y int) int // 取最大值 max = func(x, y int) int { if x > y { return x } return y } solution = func(num []int) int { length := len(num) var dpTable = make([]int, length) // 动态规划 dptable var res int // 最长子串长度 for i := 0; i < len(num); i++ { _max := 0 for j := 0; j < i; j++ { // dp[5] 为dp[1~4]中最小的统计值+1 if num[i] > num[j] { _max = max(_max, dpTable[j]) } } dpTable[i] = _max + 1 res = max(res, dpTable[i]) }
return res } return solution(nums)}
复制代码
评论