Cod sursa(job #370242)

Utilizator idomiralinIdomir Alin idomiralin Data 30 noiembrie 2009 16:56:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#include<stdlib.h>
#include<iostream>
using namespace std;

int main()
{   int n,i,k,v[100001],l[100001],max,t;
    
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&v[i]);
    
    l[n]=1;
    for(k=n-1;k>=1;k--)
         {max=0;
         for(i=k+1;i<=n;i++)
         
         if ((v[k]<v[i]) && (l[i]>max))
            max=l[i];
            l[k]=1+max;
            }
         
         max=l[1];t=1;   
         for(k=1;k<=n;k++)
         if (max<l[k]) 
         {max=l[k];
         t=k;} 
         printf("%d\n",l[t]);
         printf("%d ",v[t]);
         for (i=t+1;i<=n;i++)
         if ((v[t]<v[i]) && (l[i]==max-1))
         {printf("%d ",v[i]);
         max--;}
return 0;
}