LeetCode-300. 最长上升子序列
方法一：O(n^2)可能会超时；方法二：贪心二分法，使用lower_bound()；下面是贪心+二分算法： 由于要得到最长的递增子序列，就要让序列中的数增长率尽量小； 需要注意的事项： 1.使用lower_bound()来寻找第一个大于等于当前元素的位置，然后替换值（为什么不用upper_bound(),即寻找第一个大于当前元素的位置，eg：如果当前递增序列为1-3-5-6，当前元素为5，使用upper_bound()会找到值为6的位置并替换，使序列变为1-3-5-5，导致错误）
//包含的头文件 #include <algorithm> int LIS(vector<int>& nums) { vector<int> dp; for (auto k : nums) { //找到第一个大于等于当前元素的dp位置 auto ite = lower_bound(dp.begin(), dp.end(), k); //如果没找到，说明当前元素值大于dp序列中所有值，需要加入dp队列的末尾 if (ite == dp.end()) { dp.emplace_back(k); } else //找到了大于或则等于的位置，替换为更小的值，始终维护dp队列的值为更小的递增序列； { *ite = k; } } return dp.size(); }时间复杂度较动态规划大大降低： 如果面试时不能使用lower_bound()和upper_bound(),可以自己手动实现，代码如下：
lower_bound()的实现： 如果没找到则返回末尾元素的下一个，相当于迭代器的end()；
注意事项：
while()中的结束条件：left <= right，这样才能保证当没找到合适下标时返回end()，即left+1；先判断left，过滤掉小于target的元素；返回值为left； int My_lower_bound(const vector<int>& nums, int target) { int left = 0; //left左侧的值均<target int right = nums.size() - 1; //right右侧的值均>=target while (left <= right) { int mid = (right - left) / 2 + left; //首先判断left，这样才能排除掉小于target的下标，如果left==right时还没找到，则返回end(); if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; }upper_bound()的实现：
int My_upper_bound(const vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left<=right) { int mid = (right - left) / 2 + left; if (nums[mid] <= target) { left = mid + 1; } else { right = mid - 1; } } return left; }