Cod sursa(job #1384446)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 11 martie 2015 09:25:47
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>

using namespace std;
#define M 100001
FILE *fin=fopen("scmax.in" ,"r");
FILE *fout=fopen("scmax.out" ,"w");
int am[M] , v[M] ,prec[M] ,best[M];
int main()
{
    int maxx=0 ,maxxp=0 , i ,j  ,n ,incep ,cont ,pr;
    fscanf(fin ,"%d" ,&n);
    for(i=1;i<=n;i++)
    {
        fscanf(fin ,"%d" ,&v[i]);
    }
    best[1]=1;
    prec[1]=0;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<i;j++)
        {
            if(v[i]>v[j] && best[j]>maxx)
            {
                maxx=best[j];
                pr=j;
            }
        }
        best[i]=1+maxx;
        prec[i]=pr;
        if(best[i]>maxxp)
        {
            incep=i;
            maxxp=best[i];
        }
        maxx=0;
    }
    am[1]=v[incep];
    cont=1;
    while(prec[incep]!=0)
    {
        cont++;
        am[cont]=v[prec[incep]];
        incep=prec[incep];
    }
    fprintf(fout ,"%d\n" ,maxxp);
    for(i=cont;i>=1;i--) fprintf(fout ,"%d ", am[i]);
    return 0;
}