31最长递增子序列

最长递增子序列

动态规划的公式：

dp[i] = 1 + max( dp[j] )

其中0 <= j < i && arr[j] < arr[i]

方法1：

备忘录

使用递归树，递归终止条件为返回1

方法2：

动态规划表

for循环找前面符合条件的最小值。

方法3：

动态规划+二分（1h20m）

一个一个数字扩充进可能的最长序列，不停维护这个序列

贪婪思想：如果上升子序列的结尾越小，遍历后一个数字接上去的可能性就越大。

步骤：

如果加入的新数字比活动序列中的最小元素还要小，创建一个新序列并维护它。

如果比所有活动的序列都要大，复制一个目前最长的序列，添加到末尾。

如果介于之间的，替换末尾元素，删除等长序列。

优化：使用辅助数组仅记录末尾数字，数字的个数等于所得的最长递增子序列。