Cod sursa(job #1003967)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 1 octombrie 2013 20:15:05
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#include<algorithm>
FILE *in,*out;
using namespace std;
int  n,v[100001],i,aux[100001],j,best,pozmax,bestpoz,tata[100001];
int u,igrek,raspuns[100001];
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;
}