基本思想：

　　最长递增子序列问题原本是动态规划的经典问题，由于这个问题太经典了，所以我把它单独列在基本算法中。最简单的方法是动态规划，用一个数组dp[i]表示以nums[i]结尾的最长递增子序列的长度，对于每个dp[i]，遍历dp[k](k<i)，在所有nums[k] < nums[i]的元素中找到最大的dp[k]加1就是dp[i]，时间复杂度为O(n2)。

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

　　当然如果只是这种解法的话我也不写这篇随笔了，这道题还有一种O(nlogn）的解法，以Leetcode 300的例子为例，给一个数组[10,9,2,5,3,7,101,18]，我们维护一个lastelem数组，lastelem[i]=t表示长度为i+1的子序列的第i个元素的最小值为t。有点抽象，那就模拟一下这个例子的解答。

1. [10,9,2,5,3,7,101,18]

         ^

　　lastelem = [10]

2. [10,9,2,5,3,7,101,18]

              ^

　　lastelem = [9]　　//找到地一个比9大的数将其替换为9

3. [10,9,2,5,3,7,101,18]

                  ^

　　lastelem = [2]　　//同上

4. [10,9,2,5,3,7,101,18]

                      ^

　　lastelem = [2，5]　　//若5比最后一个数大，新填一个元素

5. [10,9,2,5,3,7,101,18]

                          ^

　　lastelem = [2，3]　　//同第二步

6. [10,9,2,5,3,7,101,18]

                              ^

　　lastelem = [2，3，7]　　//同第四步

7. [10,9,2,5,3,7,101,18]

                                    ^

　　lastelem = [2，3，7，101]　　//同第四步

8. [10,9,2,5,3,7,101,18]

                                           ^

　　lastelem = [2，3，7，18]　　//同第二步

　　所以最终最长子序列的长度为lastelem数组的长度，即4，寻找第一个比nums[i]大的数可以用二分法，所以时间复杂度为O(nlogn). 此题是Leetcode 300原题，因为是基础题型，所以不再写博客解释了。

1 class Solution { 2 public: 3     int lengthOfLIS(vector
     
      & nums) { 4         vector
      
        lastelem; 5         for(int i = 0;i != nums.size();++i){ 6             if(lastelem.empty() || nums[i] > lastelem.back()) 7                 lastelem.push_back(nums[i]); 8             else{ 9                 int start = 0;10                 int end = lastelem.size()-1;11                 while(start < end){12                     int pivot = start + (end-start)/2;13                     if(lastelem[pivot] < nums[i])14                         start = pivot+1;15                     else16                         end = pivot;17                 }18                 lastelem[start] = nums[i];19             }20         }21         return lastelem.size();22     }23 };