Cod sursa(job #1104222)

Utilizator mihail95Mihail Plesa mihail95 Data 10 februarie 2014 16:33:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<cstdio>
using namespace std;
int L[100002],poz[100002],a[100001],n,maxim=0,pozitie;
FILE *f,*g;
void init()
{
    L[n]=1;
    poz[n]=-1;
}
void citire()
{
    f=fopen("scmax.in","r");
    g=fopen("scmax.out","w");
    int i;
    fscanf(f,"%d",&n);

    for(i=1; i<=n; i++)
        fscanf(f,"%d",&a[i]);
}
void scmax()
{
    int i,j,max;
    for(i=n-1; i>=1; i--)
    {
        max=0;
        poz[i]=-1;
        for(j=i+1; j<=n; j++)
        {
            if(a[i]<a[j] && max<L[j])
            {
                max=L[j];
                poz[i]=j;
            }
        }
        L[i]=max+1;
        if(L[i]>maxim)
        {
            maxim=L[i];
            pozitie=i;
        }

    }


}
void afis()
{
    fprintf(g,"%d\n",maxim);

    while(pozitie!=-1)
    {

        fprintf(g,"%d ",a[pozitie]);
        pozitie=poz[pozitie];
    }

}
int main()
{
    citire();
    init();
    scmax();
    afis();
}