腾讯常见算法题：最长递增子序列

给你一个整数nums，求最长严格递增子序列的长度。 ？用动态规划解决问题的总体思路是：

1. 穷举分析
2. 分析寻找规律，划分子问题
3. 确定边界
4. 确定最优子结构书写方程

2.1 不好 动态规划的核心思想包括划分子问题、记住过去、减少重复计算。所以如果我们思考原来的问题：数组num[i]的最长递增子序列的长度，我们就可以思考相关的子问题。例如，原问题的子问题的最长递增子序列的长度是num[i-1]吗？ ？

自下而上的穷举过程：

• 如果nums只有一个元素10，则最长的上升子序列为[10]，长度为1。
• 如果nums需要添加元素9，则增加子序列为 [10] 或 [9]，长度为 1。
• 如果nums再加一个元素 2，则子序列的最长增量为 [10] 或 [9] 或 [2] ，长度为1.
• 如果nums又添加了一个元素5，则子序列的最长增量为[2,5]，长度为2. 3]，长度为2。
• 如果nums又添加了一个元素7，则子序列的最长增量为[2,5]，长度为2. 3]，长度为2。子序列的最长增量为[2,5,7]或[2,3,7]，长度为3。
• 如果nums再添加一个Add元素101，则子序列的最长增量为[2,5 ,7,101] 或 [2,3,7,101]，长度为 4。 ,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分析寻找规则，划分子问题

通过上面的分析我们可以发现一个规则：

如果添加了新元素nums [i] ，以 nums[i] 结尾的最长递增依赖子序列，或者 nums[i-1] 的最长递增。看到这个你是不是很高兴呢？子序列nums[i]的最长增加已经与子问题nums[i-1]的最长增加相关。

原问题数组nums[i]的最长递增子序列=子问题数组nums[i-1]的最长递增子序列/nums[i]末尾的最长递增子序列

1. 不会有这样的感觉吗？战斗已经成功一半了？但是增加nums[i]末尾的子序列如何转化为相应的子问题呢？如果nums[i]末尾子序列的增量也与nums[i-1]的最长增量相关，那就太好了。或者将 nums[i] 末尾子序列的最长增加与前一个子问题 num[j] 末尾子序列的最长增加相连（0=