Cod sursa(job #1168154)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 7 aprilie 2014 09:40:17
Problema Subsir crescator maximal Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>

using namespace std;

#define MAX 100000

long long v[MAX+1];
int best[MAX+1];
int next[MAX+1];
long long sol[MAX+1];
int main()
{
    FILE *fin,*fout;

    fin=fopen("scmax.in","r");
    fout=fopen("scmax.out","w");

    int i,n,ind,max,maxbest,indmax,j;

    fscanf(fin,"%d",&n);

    for(i=1;i<=n;i++)
        fscanf(fin,"%lld",&v[i]);

    best[1]=1;
    maxbest=1;
    ind=1;
    for(i=2;i<=n;i++)
    {
        max=0;
        for(j=i-1;j>=1;j--)
            if(v[i]>v[j]&&best[j]>max)
            {
                max=best[j];
                ind=j;
            }
        best[i]=max+1;
        if(maxbest<best[i])
        {
            maxbest=best[i];
            indmax=i;
        }
        next[i]=ind;
    }

    fprintf(fout,"%d\n",maxbest);
    i=indmax;
    j=maxbest+1;
    while(next[i]!=0)
    {
        sol[--j]=v[i];
        i=next[i];
    }
    if(i==1&&sol[1]==v[1])
        sol[1]=v[1];
    for(i=1;i<=maxbest;i++)
        fprintf(fout,"%lld ",sol[i]);

    return 0;
}