xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  n,MAX;
int  a[ 10003 ];
int  f[ 10003 ];
int  p[ 10003 ];
int  ans[ 10003 ],l;
int  main()
{
    freopen(
" maxxl.in " , " r " ,stdin);
    freopen(
" maxxl.out " , " w " ,stdout);
    scanf(
" %d " , & n);
    
for ( int  i = 1 ;i <= n; ++ i) 
        scanf(
" %d " , & a[i]);
    
int  MAX =- 1 ;
    a[
0 ] =- 0x7FFFFFFF ;
    a[n
+ 1 ] = 0x7FFFFFFF ;
    f[
0 ] = 0 ;
    
for ( int  i = n;i >= 0 ; -- i){
        f[i]
= 0 ;
        
for ( int  j = n + 1 ;j >= i + 1 ; -- j)
            
if (a[i] <= a[j])
                
if (f[i] < f[j] + 1 ){
                    f[i]
= f[j] + 1 ;
                    p[i]
= j;
                }
                
else   if (f[i] == f[j] + 1 ){
                    
if (a[j] > a[p[i]]) 
                        p[i]
= j;
                }
        
if (f[i] > MAX) MAX = f[i];
    }
    MAX
-- ;
    printf(
" %d\n " ,MAX);
    l
= 0 ;
    
int  k = 0 ;
    
while (l != MAX){
        k
= p[k];
        ans[
++ l] = a[k];
    }
    
for ( int  i = 1 ;i < l; ++ i) 
        printf(
" %d  " ,ans[i]);
    printf(
" %d\n " ,ans[l]);
    
return   0 ;
}




posted on 2009-04-21 23:43 xfstart07 阅读(280) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理