题目描述：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

 

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

 

思路分析：

思路一：根据题目的提示，利用动态规划，可以用O(N^2)的复杂度解这题。直接利用一个dp数组，用从后往前的方式存每个元素当前的最长上升序列，更新的状态转移方程就是dp[i] = max(dp[i], dp[j]+1)，这里j的取值是从i+1到dp.size()。

思路二：由于题目的进阶要求是需要将复杂度降到O(NlogN)，logn顺利成章会想到用二分查找来降低这个复杂度。实际上这部分的思想是维护一个tail数组，遍历nums数组时，每次都在tail数组中去找大于当前值的树，若有则替换，若没有则将当前值加入tail数组。进行替换的原因是在后续的查找中，可以找到更长的子序列，由于当前的tail中的元素更小了。而实际上，只有在添加新元素时会改变最长子序列的大小，因此这个tail数组的长度始终维持在当前最长子序列的长度。这里在查找数用到了二分查找，代码中直接调用了lower_bound()函数。关于这个函数的说明如下：

第一个first参数是一段连续空间的首地址，last是连续空间末端的地址，val是要查找的值。调用lower_bound()的前提是这段连续的空间里的元素是有序（递增）的。

然后lower_bound()的返回值是第一个大于等于val的值的地址，用这个地址减去first，得到的就是第一个大于等于val的值的下标

同时注意区分另一个upper_bound函数，这个返回值是第一个大于val值的地址。

 

代码：

思路一：

1 class Solution { 2 public: 3     int lengthOfLIS(vector
     
      & nums) { 4         if(nums.size()==0) 5             return 0; 6         vector
      
       dp(nums.size(), 1); 7         for(int i=nums.size()-1; i>=0; i--) 8         { 9             for(int j=i+1; j
       
         nums[i])12                 {13                     dp[i] = max(dp[i], dp[j]+1);14                 }15             }16         }17         int max = 0;18         for(int i=0; i
        
         max)21                 max = dp[i];22         }23         return max;24     }25 };
        
       
      
     

思路二：

1 class Solution { 2 public: 3     int lengthOfLIS(vector
     
      & nums) { 4         if(nums.size()==0) 5             return 0; 6         vector
      
        res; 7         for(int i=0; i