动态规划经典题之最长上升子序列最终版
“
在上一篇文章动态规划经典题之最长上升子序列中，采用动态规划的策略将时间复杂度（暴力法）由 O(n * 2^n) 降到 O(n^2)，有没有方法能将时间复杂度进一步降为 O(n * lgn)呢？答案是有的，本文采用 “贪心 + 二分查找” 的策略，将时间复杂度进一步降到 O(n * lgn)。
”
上期回顾：动态规划
在上一篇文章中，采用动态规划的策略，定义LIS(i) 为以 nums[i] 结尾且 nums[i] 必选的最长递增子序列的长度；假设当前最长递增子序列 LIS(j)（其中 j ∈ [0, i)），对于数组中的第 i 个元素nums[i]，只要满足 nums[i] > nums[j]，即可将 nums[i] 放在当前以 nums[j] 结尾的 LIS(j) 后面，以形成更长的递增子序列。
Code
// c++ 动态规划 自底向上
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
/* result 记录当前最长递增子序列的长度 */
int result = 1;
/* res[i] 表示以 nums[i] 结尾的最长递增子序列的长度，初始化为 1 */
vector<int> res(nums.size(), 1);
/* 每个 nums[i] 都可组成以自身为结尾的长度为 1 的递增子序列 */
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
/* nums[i] 可跟在 nums[j] 后组成当前更长的递增子序列 */
if (nums[i] > nums[j]) {
/* 更新 res[i] */
res[i] = max(res[i], 1 + res[j]);
}
}
/* 获取数组 nums 中最长递增子序列 */
result = max(result, res[i]);
}
return result;
}
贪心 + 二分查找
要找到数组 nums 中的最长递增子序列，则子序列递增的速度必须要尽可能小，即当前递增子序列结尾的元素越小，因为只有这样才能让更多的满足条件的元素接在其后面构成一个更长的递增子序列。这就是贪心思路。如下图示。
找数组 [0, 5, 2, 3, 6] 的最长严格递增子序列的长度
以元素 0 结尾的最长递增子序列的长度为 1，由于 5 > 0，所以 5 可以跟在 0 后面，组成当前最长递增子序列且其长度为 2。
继续往后遍历，由于 2 < 5 所以 2 不能跟在当前最长递增子序列（以 5 结尾）的后面，但可以将 2 添加在 0 的后面，因为这样会使得子序列递增的速度比较小，所以选择将数组元素 2 接在 0 后面而剔除 5，这样会更有机会获取更长的递增子序列。
同理可得
二分查找
基于上面的贪心思路，维护一个用于存放当前的最长递增子序列的数组res，并将其首元素初始化为nums[0]，不断遍历原数组，比较nums[i]与当前res中最后一个元素的大小，如果前者大于后者，则将前者加入到res中（放在res中最后一个元素的后面）构成一个更长的递增子序列；否则在数组res中查找第一个不小于前者的数，并用nums[i]替换那个数以增加res组成更长递增子序列的概率。由于数组res始终是有序的，所以可以使用二分查找。
以该题的示例 2：nums = [0, 1, 0, 3, 2, 3] 为栗子，如下图示：
初始化 res[0] 为 nums[0]
遍历nums，由于nums[1] = 1 > res[0]，将nums[1]加入到数组res中
继续遍历，此时由于nums[2] = 0 < res[1] = 1，在res中查找第一个不小于于 0 的数并替换
遍历，此时nums[3] > res[1]，将nums[3]加入res中
遍历并比较，nums[4] < res[2]，更新用nums[4]替换res[2]
最后nums[5] > res[2]，将nums[5]加入到res中，遍历结束，此时res的尺寸即为nums最长递增子序列的长度。
Show me the Code
// c++
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0) {
return 0;
}
vector<int> res; // 保存当前的最长递增子序列
res.push_back(nums[0]);
int end = 0; // 标识 res 中的最后一个元素
for(int i = 1; i < nums.size(); i ++){
if (nums[i] > res[end]) {
/* nums[i]大于res中最后一个元素，将res[i]追加到res中 */
res.push_back(nums[i]);
end++;
} else {
/* 二分查找将 nums[i] 替换进去 */
int left = 0, right = end;
while(left < right){
int mid = (left + right) / 2;
if(res[mid] < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
/* 更新res中第一个不小于nums[i]的数*/
res[left] = nums[i];
}
}
return res.size();
}腾讯云开发者
