给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是[2,3,7,101]，它的长度是4。
说明:
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
=========================================================================================
这个题之前做的时候感觉特别痛苦，再做的时候感觉没那么痛苦了，但是可能是由于注意力不集中掉进了陷阱，耽搁时间，好大一会儿才做出来。还是水平没到位。
思路： 一句话总结：统计长度为 x 的最小值 并持续维护这个表。保证数组里面记录的是长度为 x 的最小的量。
举个例子 ：10,9,2,5,3,7,101,18该怎么排
1 | 10 9 2
2 | 5 3
3 | 7
4 | 101 18
这样就维护了满足上面的关系的表了。
下面就是写代码来具体实现，用到二分查找的方法。
里面值的注意的地方有以下几点：
1. 用什么区间， 左开右闭还是左闭右开。 这个涉及到是用right来定位还是用left来定位。
2. 查找什么？ 在这里应该理清题目关系。我们要超找的数字是当前数字要替换的数字，这个数字应该满足的条件是：大于等于当前的数字。
3. 由于本数组是一个递增的数组，又是要查找大于大于等于，所以应该采用左开右闭。
5. 循环退出条件，闭区间中的元素个数小于等于1个。 如果只有一个元素说明就定位成功了，要得元素就是里面的这个。
4. 最终定位值的合法性判断。可能出现的情况有 1. 正常定位 2. 为空 3. 定位了但是不准确（例如 没有比当前值大的。
贴代码：
1 class Solution { 2 public: 3 int lengthOfLIS(vector<int>& nums) { 4 //直接用官方推荐的方法 5 //每个长度的最小结尾 数字 6 vector<int> status; 7 int len = nums.size(); 8 for(int i = 0; i<len; i++){ //每个数都轮流处理一下 9 //二分查找 查找 i 结尾的数字的位置 10 int left = -1; 11 int right = status.size()-1; //左开右闭区间 12 while(left+1<right){ 13 int mid = (left + right)/2; 14 //寻找大于 nums[i] 的第一个 15 if(status[mid] >= nums[i]){ //当前值太大了 16 right = mid; 17 }else{ 18 left = mid; 19 } 20 } 21 if(status.empty() || status[right]<nums[i]){ 22 status.push_back(nums[i]); 23 }else{ 24 status[right] = nums[i]; 25 } 26 } 27 return status.size(); 28 } 29 };
总结：思路要尽可能的清晰明了，要想到正确的思路，应该多思考，但是不能钻牛角尖。把我精华的主要内容，其它的过分的细节处理可以给临场发挥完成。
原文：https://www.cnblogs.com/xiongxinxzy/p/13271774.html