最长上升部分序列(300 )前篇中，理解了什么是DP (动态计划)，通过DP中的经典问题“最大分列和”，学习了状态转移方程应该如何定义。 本节沿袭到目前为止的分析方法，通过例题，进一步强化到目前为止的内容！
01、问题分析第300题：对最长上升子列赋予无序的整数排列，在其中找出最长上升子列的长度。示例：
如果输入： [ 10，9，2，5，3，7，101，18 ]，则输出： 4表示：的最长上升子序列为[ 2，3，7，101 ]，其长度为4。 说明：
可能有一些最长的上升子序列的组合。 输出对应的长度就可以了。 这个问题有一定的难度哦。 如果没有想法的话请回顾前一篇的学习内容！
我不建议直接看问题！
02、主题图解首先分析主题。 我要找的是http://www.Sina.com/(longestincreasingsubsequence，LIS )。 因为不要求标题连续，所以在最长上升子序列的同时，LIS可能是连续的，也可能是非连续的。的条件。 所以可以用动态计划来求解。 首先定义状态：
DP [ I ] :表示以nums [ I ]结尾的最长上升子串的长度。 假设nums为[ 1，9，5，9，3 ]，如下图所示。
我们分两种情况讨论：
当nums[i]小于前面所有元素时，如果在nums[i]之前存在比他小的元素nums[j]，其中dp[i]等于1 (即，它自己) (这个结论是正确的)，那么dp[i]是DP [ j ]
我们先得出了上述结论，但也发现了一些问题。 因为在dp[i]之前比他小的元素不一定只有一个！ 除了nums[j]之外，nums[k]，nums[p] LIS符合可以从其子问题的最优解来进行构建，因此，dp[i]不仅可以是dp[j] 1，而且可以是dp[k] 1，DP [ p ] p [ p ] 1，p ]1333338 所以为了求出dp[i]，需要找出dp[j] 1、dp[k] 1、dp[p] 1 该结论错误，比如nums[3]nums[0]，即91,但是dp[3]并不等于dp[0]+1）中的最大值。 (我之所以用3个等改成粗体字，主要是因为初学者容易在这里摔倒！ 这里强调的目的是希望你记住这个题型！ 也就是说：
DP[I]=max(DP[j]1，dp[k] 1，dp[p] 1，)可确定nums [ I ] nums [ j ] nums [ I ] nums [ k ] nums [ I ] nums [ I ] nums .
最后，只要找到dp序列的最大值，就会成为我们正在寻找的答案。 分析结束后，我们画出图：
03、通过Go语言示例以上分析，可以得到代码：
funclengthoflis(nums(int ) int ) iflen ) nums )1) return0) DP:=make ) ) int，len ) result 3360=1ff ilen i {dp[i]=1for j :=0； j i； j { ifnums [ j ] nums [ I ] { DP [ I ]=max (DP [ j ] 1，DP[I]}}result=max(result，DP [ I ] ) )