dp[j] = max(dp[k]+1,dp[j])(0<k<j&a[j]>a[k])

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int inf = (1<<31)-1;const int MAXN = 5e5+10;int dp[MAXN];int a[MAXN];int main(){ int n; int mmax; while(~scanf("%d",&n)){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[1] = 1; mmax = 1; for(int i=2;i<=n;i++){ for(int j=1;j
             
              a[j]){ dp[i] = max(dp[j]+1,dp[i]); } } mmax = max(mmax,dp[i]); } cout<
              
               <
              
             
            
           
          
         
        
       
      

 其实还有一种O(n*lgn)+O(n^2)的算法，先把原序列排序,再寻找LCS