动态规划之最长上升子序列

题目

给定一个无序的整数数组,找到其中最长上升子序列的长度.

思路

在索引是n位置的最长上升子序列是:
如果n位置处的值大于n-1处的值,那么等于n-1处的长度加1
如果n位置处的值小于等于n-1处的值,那么等于1

状态转移方程

if nums[i] > nums[i-1] {
    dp[i] = dp[i-1] + 1
} else {
    dp[i] = 1
}

最终代码

func calc(nums []int) int {
    if len(nums) < 1 {
        return 0
    }
    dp := make([]int, len(nums))
    result := 1
    dp[0] = 1
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            dp[i] = dp[i-1] + 1
        } else {
            dp[i] = 1
        }
        result = max(result, dp[i])
    }
    return result
}

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