NC91 最长递增子序列 👌

//  时间On^2, 空间On，    答案不对，应该构造数组的下标不对
func LIS( arr []int ) []int {
    if len(arr) == 0 {
        return arr
    }
    n := len(arr)
    res := 0
    cur := []int{}
    dp := make([]int, n+1)
    for i := 1; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if arr[j] < arr[i] {
                dp[i] = max(dp[i], dp[i] + 1)
            }
        }
        if dp[i] > res {
            res = dp[i]
            cur = append(cur, arr[i])
        }
    }
    return cur
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}