day43 | 最长子序列

300.最长递增子序列

首先是动态规划的方法 if nums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1) 每遍历一个 i 的时候就需要遍历前面的所有num，来更新最长的长度。复杂度是O^2

然后是 DAG 的算法， 求最长递增子序列的过程可以看做是这样的图 426783

一个注意点就是，我们维持一个当前最小的子序列，如果后续有比它还小的树，则需要更新当前最小的子序列，在图中的例子就是已经有 4 了 同时要更新一个 2，尽管 4 的子序列长度可能会比 2 更长，但后续可能存在多个比 2 大数字最终导致 2 的子序列更长。

然后在更新 2 的过程我们实际上是在一个有序list 里找到第一个比它大的数字。这可以用二分法来解决。

此处可以参考hello 算法里面的查找插入点。一个显而易见的想法就是二分结束时一定有：i 指向首个大于 target 的元素，j 指向首个小于 target 的元素。易得当数组不包含 target 时，插入索引为 i 。

674. 最长连续递增序列

因为是递增的所以只用考虑 i-1的情况

718. 最长重复子数组

为了方便初始化，所以dp[i]实际上表示的以i-1为结尾的长度。 需要注意的是dp[i][j]依赖 dp[i-1][j-1]进行递推，而 dp[i-1]的含义实际上是 i-2 结尾的长度。 此处容易和nums[i-1]的i-1混淆