最长上升子序列LIS问题属于动态规划的初级问题，用纯动态规划的方法来求解的时间复杂度是O(n^2)。但是如果加上二叉搜索的方法，那么时间复杂度可以降到nlog(n)。

　 具体分析参考：

　 代码：

#include 
     
      using namespace std;int LIS_nlogn(int *arr, int len){    int *LIS = new int[len];    //LIS[i]存储的是每个最长长度i的最小结尾,即在arr里的最小结尾    for (int i = 0; i < len; i++)    {        LIS[i] = -1;    }    int maxLen = 1;    //记录最长上升子串的最大长度    LIS[0] = arr[0];    for (int i = 0; i < len; ++i)    {        int low = 0, high = maxLen, mid;        while (low <= high)        {            mid = (low + high)/2;            if (LIS[mid] < arr[i])            {                low = mid + 1;            }             else            {                high = mid - 1;            }        }        LIS[low] = arr[i];    //插入元素到相应的位置        if (low > maxLen)        {            maxLen++;        }    }    delete LIS;    return maxLen;}int main(){    int arr[] = {
   2,1,5,3,6,4,8,9,7};    int len = 9;    int ret;    ret = LIS_nlogn(arr, len);    cout<
      
       <