给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
实例1：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
实例2：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
输入：nums = [0,1,0,3,2,3]
输出：4
思路：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
这道题是求最值问题，可以使用动态规划解决。动态规划的解题整体思路就是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
穷举分析 分析找规律，拆分子问题 确定边界 确定最优子结构 写出状态转移方程
2.1 穷举分析
动态规划的核心思想包括拆分子问题，记住过往，减少重复计算。所以我们在思考原问题：数组num[i]的最长递增子序列长度时，可以思考下相关子问题，比如原问题是否跟子问题num[i-1]的最长递增子序列长度有关呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
自底向上的穷举过程：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
当nums只有一个元素10时，最长递增子序列是[10],长度是1. 当nums需要加入一个元素9时，最长递增子序列是[10]或者[9],长度是1。 当nums再加入一个元素2时，最长递增子序列是[10]或者[9]或者[2],长度是1。 当nums再加入一个元素5时，最长递增子序列是[2,5],长度是2。 当nums再加入一个元素3时，最长递增子序列是[2,5]或者[2,3],长度是2。 当nums再加入一个元素7时，,最长递增子序列是[2,5,7]或者[2,3,7],长度是3。 当nums再加入一个元素101时，最长递增子序列是[2,5,7,101]或者[2,3,7,101],长度是4。 当nums再加入一个元素18时，最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4。 当nums再加入一个元素7时,最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4.
2.2 分析找规律，拆分子问题
通过上面分析，我们可以发现一个规律：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
如果新加入一个元素nums[i], 最长递增子序列要么是以nums[i]结尾的递增子序列，要么就是nums[i-1]的最长递增子序列。看到这个，是不是很开心，nums[i]的最长递增子序列已经跟子问题 nums[i-1]的最长递增子序列有关联了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
原问题数组nums[i]的最长递增子序列 = 子问题数组nums[i-1]的最长递增子序列/nums[i]结尾的最长递增子序列文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
是不是感觉成功了一半呢？但是如何把nums[i]结尾的递增子序列也转化为对应的子问题呢？要是nums[i]结尾的递增子序列也跟nums[i-1]的最长递增子序列有关就好了。又或者nums[i]结尾的最长递增子序列，跟前面子问题num[j]（0=<j<i）结尾的最长递增子序列有关就好了，带着这个想法，我们又回头看看穷举的过程：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
nums[i]的最长递增子序列，不就是从以数组num[i]每个元素结尾的最长子序列集合，取元素最多（也就是长度最长）那个嘛，所以原问题，我们转化成求出以数组nums每个元素结尾的最长子序列集合，再取最大值嘛。哈哈，想到这，我们就可以用dp[i]表示以num[i]这个数结尾的最长递增子序列的长度啦，然后再来看看其中的规律：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
其实，nums[i]结尾的自增子序列，只要找到比nums[i]小的子序列，加上nums[i] 就可以啦。显然，可能形成多种新的子序列，我们选最长那个，就是dp[i]的值啦文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
nums[3]=5,以5结尾的最长子序列就是[2,5],因为从数组下标0到3遍历，只找到了子序列[2]比5小，所以就是[2]+[5]啦，即dp[4]=2 nums[4]=3,以3结尾的最长子序列就是[2,3],因为从数组下标0到4遍历，只找到了子序列[2]比3小，所以就是[2]+[3]啦，即dp[4]=2 nums[5]=7，以7结尾的最长子序列就是[2,5,7]和[2,3,7],因为从数组下标0到5遍历，找到2,5和3都比7小，所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]这些子序列，最长子序列就是[2,5,7]和[2,3,7]，它俩不就是以5结尾和3结尾的最长递增子序列+[7]来的嘛！所以，dp[5]=3 =dp[3]+1=dp[4]+1。
很显然有这个规律：一个以nums[i]结尾的数组nums文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
如果存在j属于区间[0，i-1],并且num[i]>num[j]的话，则有:dp(i) =max(dp(j))+1。
2.3 确定边界
当nums数组只有一个元素时，最长递增子序列的长度dp(1)=1,当nums数组有两个元素时，dp(2) =2或者1， 因此边界就是dp(1)=1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
2.4 确定最优子结构
从2.2 穷举分析找规律，我们可以得出，以下的最优结构：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
dp(i) =max(dp(j))+1，存在j属于区间[0，i-1],并且num[i]>num[j]。
max(dp(j)) 就是最优子结构。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
2.5 写出状态转移方程
通过前面分析，我们就可以得出状态转移方程啦：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
所以数组nums[i]的最长递增子序列就是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
最长递增子序列 =max(dp[i])
完整代码实现如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23740.html
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
//初始化就是边界情况
dp[0] = 1;
int maxans = 1;
//自底向上遍历
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
//从下标0到i遍历
for (int j = 0; j < i; j++) {
//找到前面比nums[i]小的数nums[j],即有dp[i]= dp[j]+1
if (nums[j] < nums[i]) {
//因为会有多个小于nums[i]的数，也就是会存在多种组合了嘛，我们就取最大放到dp[i]
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}