Cod sursa(job #676102)

Utilizator StefanLacheStefan Lache StefanLache Data 8 februarie 2012 17:53:44
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
int l[100000],v[100000];
int main()
{
    int i,j,n,max;
    FILE *f=fopen("scmax.in","rt");
    FILE *g=fopen("scmax.out","wt");
    fscanf(f,"%i",&n);
    for(i=0;i<n;i++)
        fscanf(f,"%i",&v[i]);
    l[n-1]=1;                               //de la ultimul element se poate forma un sir de lungime 1
    for(i=n-2;i>=0;i--)
    {
        max=0;
        for(j=i+1;j<n;j++)                   //calculam pt fiecare nr scmax care se poate forma de la el
            if(v[j]>v[i] && l[j]>max)
                max=l[j];
        l[i]=max + 1;
    }
    max=l[0];
    int inc=0;
    for(i=1;i<n;i++)
        if(l[i]>max)
        {
            max=l[i];
            inc=i;
        }
    fprintf(g,"%i\n%i ",max,v[inc]);

    for(i=inc+1;i<n;i++)
        if(v[i]>v[inc]&&l[i]==max-1)
            {
                fprintf(g,"%i ",v[i]);
                max--;
            }
    return 0;
}