题解 | #最长上升子序列(一)#

package main

func LIS( arr []int ) int {
    // write code here dp[i] 表示以 i 结尾的子数组的最长上升子序列
    if len(arr) == 0 {
        return 0
    }
    n, ans := len(arr), 1
    dp := make([]int, n)
    for i := 0; i < n; i++ { // 每个数组最少代表 1 个子序列长度
        dp[i] = 1
    }
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if arr[j] < arr[i] {
                dp[i] = max(dp[i], dp[j] + 1)
                ans = max(ans, dp[i])
            }
        }
    }
    return ans
}
func max(a, b int) int { if a < b { return b }; return a }