Cod sursa(job #690321)

Utilizator StefanLacheStefan Lache StefanLache Data 25 februarie 2012 15:41:46
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
int lung[100000],v[100000],leg[100000];
void afis_rec(FILE *g,int ult_completat,int poz)
{
    if(ult_completat==0)
        return;
    afis_rec(g,--ult_completat,leg[poz]);
    fprintf(g,"%i ",v[poz]);
}
int main()
{
    int n,i,j;
    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]);
    fclose(f);
    lung[0]=0;
    int ult_completat=0;
    leg[0]=-1;
    for(i=1;i<n;i++)
        {
            if(v[i]>v[lung[ult_completat]])
                {
                    lung[++ult_completat]=i;
                    leg[i]=lung[ult_completat-1];
                }
                else
                {
                    j=ult_completat;
                    while(v[lung[j]]>=v[i] && j!=-1)
                        j--;
                    lung[++j] = i;
                    if(j==0)
                        leg[i]=-1;
                        else
                        leg[i]=lung[ult_completat-1];
                }
        }
    fprintf(g,"%i\n",ult_completat+1);
   int poz=lung[ult_completat];
   ult_completat++;
   afis_rec(g,ult_completat,poz);
    return 0;
}