动态规划之求一个序列的最长递增子序列
dp[i] 必须以i结尾的情况下，最长递增子序列的长度
思路2： O（n*logn）
只是对第一步建立dp的过程进行了优化，第二部不变
建立辅助数组h，h[i]表示，长度为i+1的递增子序列的最小末尾，所以说h数组的值均来自原数组
dp依旧表示序列以i元素结尾的情况下，最长递增子序列的长度
h用黑色字体，h的更新用品红底色
h的更新策略为：在将正在处理的元素和h中的元素进行比较（二分查找的方法），找到第一个大于当前元素的元素，进行替换，
如果不存在，则当前元素写入h数组，且当前元素在h中的下标就是dp数组中对应的值
dp蓝色字体表示，dp的更新用黄色底色
2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 |
1 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
1 | 1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 | 1 | 2 |
|
|
|
|
|
|
1 | 5 |
|
|
|
|
|
|
|
1 | 1 | 2 | 2 |
|
|
|
|
|
1 | 3 |
|
|
|
|
|
|
|
1 | 1 | 2 | 2 | 3 |
|
|
|
|
1 | 3 | 6 |
|
|
|
|
|
|
1 | 1 | 2 | 2 | 3 | 3 |
|
|
|
1 | 3 | 4 |
|
|
|
|
|
|
1 | 1 | 2 | 2 | 3 | 3 | 4 |
|
|
1 | 3 | 4 | 8 |
|
|
|
|
|
1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 |
|
1 | 3 | 4 | 8 | 9 |
|
|
|
|
1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 4 |
1 | 3 | 4 | 7 | 9 |
|
|
|
|