给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路一：动态规划。 初始条件，f[i] = 1，即每个数字都是自己的最长公共子序列 转移方程：
代码：
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> f(n,0); for(int j = 0;j < n;++j) { f[j] = 1;//每个数都是自己的最长上升子序列 for(int i = 0;i < j;++i) { if(nums[i] < nums[j]) { f[j] = max(f[j],f[i] + 1); } } } return *max_element(f.begin(),f.end()); } };时间复杂度：O(n^2)其中 n 为数组nums 的长度。动态规划的状态数为 n，计算状态 f[i]时，需要 O(n) 的时间遍历 f[0]、f[1]、f[2]...f[n-1]的所有状态，所以总时间复杂度为O(n^2)。
这里再补充一点小知识：如果我们需要将最长上升子序列打印出来，则可以用如下代码，具体解释看代码注解。
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> f(n,0); vector<int> pi(n,-1); int p = 0; for(int j = 0;j < n;++j) { f[j] = 1;//每个数都是自己的最长上升子序列 for(int i = 0;i < j;++i) { if(nums[i] < nums[j]) { f[j] = max(f[j],f[i] + 1); if(f[j] == f[i]+1)//确实是更新而来 { pi[j] = i; } } } res = max(res,f[j]) if(f[j] == res) { pi= j } } vector<int> seq(res,0);//seq里面存放 for(int i = res -1;i>=0;--i) { seq[i] = nums[p]; p = pi[p]; } } };思路二：贪心+二分查找
维护一个数组tail，当出现的数大于这个数组直接append，否则替换掉数组中大于等于这个数的最小值。 最后tail的长度就是最长上升子序列的长度 而tail数组是一个有序数组，使用二分查找复杂度为O（log n）
每一次来一个新的数 num，就找 tail 数组中第一个大于等于 num 的那个数，试图让它变小，以致于新来的数有更多的可能性接在它后面，成为一个更长的“上升子序列”，这是“贪心算法”的思想。
复杂度分析 时间复杂度：O（nlogn） 空间复杂度：O（n）
代码实现： 注意这里的二分查找实现的语义：lo指示的是大于等于待查找元素的最小秩。
class Solution { public: //返回的是不小于目标值元素的最小的秩 int binarySearch(vector<int>& nums,int lo,int hi,int target) { while(lo < hi) { int mid = (lo + hi) >> 1; if(target <= nums[mid]) { hi = mid; } else { lo = mid + 1; } } return lo; } int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> tail{nums[0]};// 第i个位置上的元素是长度为i+1的最长上升子序列的末尾元素最小值 for(int i = 1;i < nums.size();++i) { int x = nums[i]; int left = 0,right = tail.size(); int index = binarySearch(tail,left,right,x); if(index == tail.size())//查找失败时 lo指向数组末尾的下一个元素（即无穷大哨兵） { tail.push_back(nums[i]);//如果比末尾元素大 则加入数组 } else { tail[index] = nums[i];//否则 替换大于x的最小秩的元素 } } return tail.size(); } };