前言
开设专栏主要是为了能够记录自己刷题过程中的所思所想,以便能够在未来开发工作中能够快速温习并应用。如果文章能够带给大家一些启发,那便是意外之喜了。
题目描述
leecode-300 最长递增子串
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
题解
func lengthOfLIS(nums []int) int {
m := make([]int, len(nums))
res := 0
for i := 0; i < len(nums); i++ {
counter := 1
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
counter = Max(counter, m[j]+1)
}
}
m[i] = counter
res = Max(res, counter)
}
return res
}
func Max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
核心:动态规划
首先,我们应该思考的是,对于序列中的某一个元素i而言,它的存在会对我们求解的结果有影响吗?以序列0316227为例,我们来分析解题思路:
如上图所示,以0为末尾的最长严格递增子序列是0,以3为末尾的最长子序列是03.我们来分析第三个元素1。当这个元素作为序列末尾的时候,他的最长递增子序列的长度我们该怎么计算。显而易见的是,0<1,3>1,我们是不是可以得出这样的结论,第三个元素1可以添加到第一个元素为末端的子序列的后边,这时的子序列为01,同样符合严格递增子序列的定义。我们可以叠加以第一个元素为末端的严格递增子序列的长度+1,就是以第三个元素为末端的递增子序列的长度。
我们将目光转移到第四个元素,6>1,6>3,6>0,那么以6可以添加到以0/3/1为末端的最长递增子序列的末端,以6为末端的最长递增子序列就是上面以0/3/1为末端的最长递增子序列中的最大值。依次类推,我们可以得出以下的求解过程:
上图的DP[i]指的是:以第i个元素为序列末端时的最长严格递增子序列长度。上图展示了该值的推导过程。当我们遍历得出DP[i]的值的时候,我们就可以推导该题的全部可能场景。原体中提及的一个整数数组 nums ,找到其中最长严格递增子序列的长度的题解,一定符合上文推导中提及的假设:即这个题解一定是以第i个元素为序列末端时的最长严格递增子序列长度,那么我求出DP[i]的最大值,就是我们最终的题解。
后记
算法学习,前路慢慢,与君共勉
无他,唯手熟尔