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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @return int整型
*/
func LIS( arr []int ) int {
    // 例子 [6,3,1,5,2,3,7] 最长上升子序列为 [1,2,3,7]
    // dp[i] 表示以arr[i]结尾的最长严格上升子序列的长度
    // 遍历 arr[i]之前的所有元素 arr[j] (j < i) 如果 arr[j] < arr[i],
    // 就意味着 arr[i] ～ arr[j] 形成上升子序列，形成一个新的上升子序列
    // dp[i] = max(dp[i],dp[j]+1)

    n := len(arr)
    if n == 0 {
        return 0
    }

    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    maxLen := 1
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if arr[j] < arr[i] {
                dp[i] = max(dp[i],dp[j] + 1)
            }
        }
        maxLen = max(maxLen,dp[i])
    }
    return maxLen
}

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