Cod sursa(job #324065)

Utilizator cristikIvan Cristian cristik Data 14 iunie 2009 15:40:25
Problema Subsir crescator maximal Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 0.63 kb
#include <stdio.h>
int i,j,poz[100001],l[100001],n,a[100001],max,pozmax;
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++) scanf("%d",&a[i]);
    l[n]=1; poz[n]=-1;
    for(i=n-1; i>=1; i--)
     for(l[i]=1,poz[i]=-1,j=i+1; j<=n; j++)
      if(a[i]<=a[j] && l[i]<l[j]+1)
      {
          l[i]=1+l[j];
          poz[i]=j;
      }
    max=l[1];pozmax=1;
    for(i=2; i<=n; i++)
     if(max<l[i])
     {
         max=l[i];
         pozmax=i;
     }
     printf("%d\n",max);
    for(i=pozmax; i!=-1; i=poz[i]) printf("%d ",a[i]);
    return 0;
}