算法刷题 —— 最长递增子序列(Leetcode 300)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package main

func main() {

}

// O(n2)
func lengthOfLIS(nums []int) int {
    res := math.MinInt
    dp := make([]int,len(nums))
    for i := 0 ; i < len(nums) ; i++ {
        dp[i] = 1
    }
    for i := 1 ; i < len(nums) ; i++ {
        for j := 0 ; j < i ; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[j]+1,dp[i])
            }
        }
    }
    for i := 0 ; i < len(nums) ; i++ {
        res = max(res,dp[i])
    }
    return res
}