题解 | #Redraiment的走法#

package main

import (
    "fmt"
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxStep(nums []int) int {
    var step int
    size := len(nums)

    // dp[i]: 表示到下标i的最多步数
    dp := make([]int, size)

    // 初始化
    for i:=0; i<size; i++ {
        dp[i] = 1
    }

    // 动态转移方程
    for i:=1; i<size; i++ {
        for j:=0; j<i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j] + 1)
                step = max(step, dp[i])
            }
        }
    }

    return step
}

func main() {
    var n int
    fmt.Scan(&n)

    var nums []int
    for i:=0; i<n; i++ {
        var num int
        fmt.Scan(&num)
        nums = append(nums, num)
    }

    fmt.Println(maxStep(nums))
}

// 本题输入一行整数，所以采用：fmt.Scan(&n)