力扣300:最长递增子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路

想要得到最长的递增子序列长度我们必须先能判断递增子序列，这道题没有严格要求是连续的子序列反而是让难度更高了，想要得到递增的子序列我们首先要判断这个位置前面是否有比它还小的值，如果有子序列的长度就可以在原本的基础上进行+1了。但是一个数组的子序列有很多我们应该在哪个子序列原本的基础上对长度进行++呢？这就要引入题目的另外一个条件了最长递增子序列，所以我们可以构造一个新数组长度和原数组相同，新数组中每个位置存储着原数组以该位置为结尾的最长递增子序列的长度。当我们遇到一个新位置时我们就遍历其前面的所有位置如果有位置的值小于当前值我们就通过判断来得到当前位置的最长递归子序列的长度。判断条件就是取当前位置在新数组的值以及前置位置在新数组的值+1中的最大值，也就是我们假设当前位置为i，前置位置为j，新数组为newnums。那么判断条件就是newnums[i] = max(newnums[i],newnums[j]+1)。我们再定义一个变量来得到循环中的newnums[i]的最大值即可。
我们在这题使用的思想是动态规划，我们可以发现新数组的每个位置的都是等于记住了以当前位置为结尾时的答案也就是最长递增子序列的长度。所有动态规划的思想就是构建一个新数组，这个数组里存储的值就是以当前位置为结尾时的答案，再通过状态转换方程来得到下一个位置的答案以此类推。

代码