思路: 由于一般的动态规划时间复杂度是O(n^2)（哈哈哈哈 第一次用的就是这个！）用在这里由于n最大为50000 所以会超时 到这里我们可以用一个数组来动态维护这个最长上升的子序列，将你要输入的子序列一个一个按升序存入数组 如果发现当前要存入的数字x比数组最后一个还要大 那么直接存入数组，否则就将数组中按升序第一个大于x的数 用x替换掉（这里的替换我们可以用二分搜索来进行） 由于二分搜索的时间复杂度是log(n) 所以总的时间复杂度为O(n log(n) )； 下面举个例子

　　例如 -6 4 -2 10 5 ，我们假设用p数组来存储这个序列 那么 p[0] = -6; 我们发现4 比-6大我们就直接将之存入 则 p[1] = 4，现在到 -2 我们用将数组总第一个大于-2的数用-2替换掉 则 p[1] = -2 ,现在p[]= ( -6,-2 ); 之后再用同样的方法 最后的结果是p[] = ( -6 , -2 , 5 ), 这里可以得知 （-6，-2，10） 的长度与前面的答案一致 但是因为5比10 小 所以如果后面还有数可以继续拓展的话 很明显 5 之后可以存的更多的数(  好像有点啰嗦！还是直接上代码吧) 

1 /* 2 //我们先来看一下第一次的超时代码  3 #include
     
       4 #include
      
        5 #include
       
         6   7 using namespace std; 8 typedef long long LL; 9 const LL maxn = 50005;10 LL dp[maxn];11 LL m[maxn];12 LL n;13 int main()14 {15     cin>>n;16     for(int i=1;i<=n;i++)17     {18         cin>>m[i];19         dp[i] = 1;20     }21     for(int i=2;i<=n;i++)22         for(int j=i;j>=1;j--)23             if(m[i]>m[j])24                 dp[i] = max(dp[i],dp[j]+1);25     LL ans = 0;26     for(int i=1;i<=n;i++)27         ans = max(ans,dp[i]);28     cout<
        
         <
         
          36 #include
          
           37 #include
           
            38 39 using namespace std;40 const int maxn = 50005;41 int p[maxn],a[maxn];42 int n,len = 0;43 int main()44 {45 cin>>n;46 for(int i=0;i
            
             >a[i];48 p[0] = a[0];49 for(int i=1;i
             
              p[len])//当前数大于数组末尾的数 直接存入 52 p[++len] = a[i];53 else54 {55 int pos = upper_bound(p,p+len,a[i]) - p;56 p[pos] = a[i];//将第一个大于当前数的目标用当前数替换掉 57 }58 }59 cout<