Cod sursa(job #1620629)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 29 februarie 2016 11:30:07
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<algorithm>
FILE *in,*out;
using namespace std;
int  n,v[100007],i,aux[100007],j,best,pozmax,bestpoz,tata[100007];
int u,igrek,raspuns[100007];
int main()
{
    in=fopen("scmax.in","rt");
    out=fopen("scmax.out","wt");
    fscanf(in,"%d",&n);
    aux[1]=1;
    int maxim=1;
    for(i=1;i<=n;i++)
        fscanf(in,"%d",&v[i]);

    for(i=2;i<n;i++)
    {
        best=0;
        bestpoz=0;
        for(j=1;j<i;j++)
        {
            if(v[i]>v[j])
            {
                if(aux[j]>best)
                {
                    best=aux[j];
                    bestpoz=j;
                }

            }
        }
        aux[i]=best+1;
        tata[i]=bestpoz;
        if(aux[i]>maxim)
        {
            maxim=aux[i];
            pozmax=i;

        }
    }

    fprintf(out,"%d\n",maxim);

    igrek=pozmax;
    while(tata[igrek])
    {
        raspuns[++u]=igrek;
        igrek=tata[igrek];
    }
    raspuns[++u]=igrek;
    for(i=u;i>=1;i--)
        fprintf(out,"%d ",v[raspuns[i]]);
    fclose(in);
    fclose(out);
    return 0;
}