300.M 最长递增子序列

Problem: 300. 最长递增子序列

思路

动态规划。

令dp[i]表示以i即为的最长递增子序列的长度，则：对于j∈[0, i-1]的区间，有：

if nums[i] > nums[j]:
    dp[i] = max(dp[i], dp[j] + 1)

在用一个变量继续dp数组的最大值，即为所求。

Code

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	dp := make([]int, len(nums))
	maxLen := 1
	for i := 0; i < len(nums); i++ {
		dp[i] = 1 //设置初始值为1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				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
}