给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
|
这道题目的关键是找到切入点,$dp(i)$ 指的是以第 i 个元素结尾的最长递增序列, 用数学公式表示如下:
表1 模拟
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
nums[i] |
10 |
9 |
2 |
5 |
3 |
7 |
101 |
18 |
dp(i) |
1 |
1 |
1 |
2 |
2 |
3 |
4 |
4 |
代码:
func lengthOfLIS(nums []int) int { l := len(nums) if l == 0 { return 0 } dp := make([]int, l) for i := 0; i < l; i++ { dp[i] = 1 }
res := 1 for i := 0; i < l; i++ {
for j := i - 1; j >= 0; j-- { if nums[j] < nums[i] { dp[i] = max(dp[i], 1 + dp[j]) } } res = max(res, dp[i]) } return res }
func max(a, b int) int { if a > b { return a } else { return b } }
|