Cod sursa(job #628449)

Utilizator Daniel30daniel Daniel30 Data 1 noiembrie 2011 14:07:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
#define NMAX 100001
using namespace std;
int a[NMAX],n,max=1,l[NMAX],p;
void cit()
{freopen("scmax.in","rt",stdin);
 freopen("scmax.out","wt",stdout);
 scanf("%d",&n);
 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}
int main()
{cit();
 l[n]=1;
 for(int i=n-1;i>=1;i--)
	 {int m=0;
	  for(int j=i+1;j<=n;j++) 
		 if(a[j]>a[i] && m<l[j] ) m=l[j]; 
	  l[i]=m+1;
	  if(max<l[i]) {max=l[i];p=i;}
	 }
 printf("%d\n",max);
 do{printf("%d ",a[p]);
    int j=p+1,w=1;
    while(j<=n&&w) 
		{if( a[p]<a[j]) 
		  if(l[p]==1+l[j])
			{p=j;w=0;};
		 j++;
		}
	max--;
   }while(max); 
 printf("\n");
 return 0;
}