最长单调递增子序列的三种解法

找出由n个数组成的序列的最长单调递增子序列

解法一：转化成LCS问题求解，时间复杂度为O(n*n).

思路：原序列为A，把A按升序排序得到序列B，求出A，B序列的最长公共子序列，即为A的最长单调递增子序列。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; //转化成LCS问题，时间复杂度O(n*n) int d[105][105]; int a[105]; int b[105]; int c[105][105]; void LCS_path(int i,int j) //打印路径 { if(i==0||j==0) return; if(c[i][j]==1) { LCS_path(i-1,j-1); cout<
      
       >m; while(m--) { cin>>n; for(i=1; i<=n; i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+n+1); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(a[i]==b[j]) { d[i][j]=1+d[i-1][j-1]; c[i][j]=1; } else if(d[i-1][j]>d[i][j-1]) { d[i][j]=d[i-1][j]; c[i][j]=2; } else { d[i][j]=d[i][j-1]; c[i][j]=3; } } } LCS_path(n,n); cout<
       
        
 解法二：设d[i]为以第i个元素结尾的最长递增子序列的长度，则d[i]=max{0,d[j] | j
        
         
 
         





 
         
#include
          
           
#include
           
             #include
            
              using namespace std; int d[105]; int a[105]; int main() { int i,j,n,m; //freopen("d:\\test.txt","r",stdin); cin>>m; while(m--) { cin>>n; for(i=0; i
             
              >a[i]; } d[0]=1; int ans=0; for(i=1;i
              
               =0;j--) { if(a[i]>a[j]) { if(Max
               
                
 解法三：设d[i]为以第i个元素结尾的最长递增子序列的长度。假设已经计算出的两个状态p和q满足a[p]
                
                 p且i>q)来说，p一定比q好。所以此时只保留p一定不会丢失最优解。所以对于相同的d值，只需保留a[i]最小的一个。g[i]表示d值为i的最小状态编号(g[i]初始化为正无穷)。 
                 
 
                 
在给定状态 i 时,可用二分查找找到满足g[k]>=a[i]的第一个下标k,d[i]=k,此时a[i]
                   
                  
                 
 
                 
#include
                  
                   
#include
                   
                     #include
                    
                      using namespace std; const int INF=1e9; int d[105]; int a[105]; int g[105]; int main() { int i,j,n,m; //freopen("d:\\test.txt","r",stdin); cin>>m; while(m--) { cin>>n; for(i=0; i
                     
                      >a[i]; } int ans=0; for(i=1;i<=n;i++) g[i]=INF; //初始化g[i] for(i=0;i