力扣300-最长递增子序列（Java详细题解）
题目链接：300. 最长递增子序列 - 力扣（LeetCode）
前情提要：
本题是子序列问题的开始篇，接下来我将更新子序列篇章的dp问题。
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。
题目思路:
本题题目描述要求我们对数组中找到最长的递增子序列，子序列可以是不连续的元素。
话不多说，直接用dp五部曲系统分析一下。
1.确定dp数组和i下标的含义。
本题要求最长严格递增子序列的长度，所以dp[i]定义为以下标i结尾的数组最长递增子序列的长度。
2.确定递推公式。
本题是求的递增的子序列，所以肯定是要让用nums[j] 来遍历nums[i]。
如果nums[i] > nums[j]才是递增的，就可以添加到我们的结果集中。
那么怎么才能得出本数组的最长递增长序列呢？
其实有点像力扣139的单词拆分，如果j到i这段是递增（nums[i] > nums[j])的，那么i的最长递增子序列就为dp[j] + 1。
就为之前以j为结尾的最长递增子序列加上nuns[i]这个元素，所以就为dp[j] + 1。
因为要求最长递增长序列，所以需要对dp[i] 取一个最大。
dp[i] = Math.max(dp[j] + 1,dp[i]);
3.dp初始化。
由dp数组可以看出，dp[i]是指以下标i结尾的数组最长递增子序列的长度。所以每个dp[i]的最长递增子序列都最少为1。
那么我们就将整个数组都初始化为1。
4.确定dp的遍历顺序。
由递推公式可以看出 dp[i] = Math.max(dp[j] + 1,dp[i]);，而dp[j]又是要遍历dp[i] ，所以遍历顺序只能是从前往后遍历。
5.如果没有ac打印dp数组 利于debug。
最终代码：
class Solution {public int lengthOfLIS(int[] nums) {//dp数组定义 以nums[i]为结尾的最长子序列的长度//在这里要对nums长度为1进行特判，因为如果长度为1就不会进入循环 而我的result 是初始化为0 所以会为0//但是如果nums长度为1 他的最长递增子序列就是他本身 所以长度为1 你初始化result = 1也可以if(nums.length == 1)return 1;//该题关键就是递推公式 int [] dp = new int [nums.length + 1];int result = 0;Arrays.fill(dp,1);for(int i = 1;i < nums.length;i ++){for(int j = 0;j < i;j ++){if(nums[i] > nums[j]){dp[i] = Math.max(dp[j] + 1,dp[i]);}}//收集结果的地方 可能不是最后一个位置 可能是任意位置 所以要对任意位置结尾的最长子序列的长度取一个最值result = Math.max(result,dp[i]);}return result;}
}
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。
我很乐意为你解答。那么我们下篇再见！