Cod sursa(job #1384461)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 11 martie 2015 09:32:27
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 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];
void subsir(int p)
{
    if(prec[p]!=0) subsir(prec[p]);
    fprintf(fout , "%d " , v[p]);
}
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;
        pr=0;
    }


    fprintf(fout ,"%d\n" ,maxxp);
    subsir(incep);
    return 0;
}