Cod sursa(job #499281)

Utilizator JulotMMihnea M. JulotM Data 9 noiembrie 2010 15:10:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include "cstdio"

using namespace std;

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

int a[100001],l[100001],x[100001];

int main()
{
    int n;
    fscanf(fin,"%d",&n);

    for(int i=0;i<n;i++)
        fscanf(fin,"%d",&a[i]);

    for(int i=n-1;i>=0;i--)
    {
        int max=0;
        int ok=0;

        for(int j=i;j<n;j++)
            if(a[i]<a[j])
                ok=1;
        if(ok==0)
            l[i]=1;
        else
        {
            for(int j=i+1;j<n;j++)
                if(l[j]>max && a[j]>a[i])
                    max=l[j];
            l[i]=1+max;
        }
    }

    int p;
    int max=0;
    for(int i=0;i<n;i++)
        if(l[i]>max)
        {
            max=l[i];
            p=i;
        }


    int nr=0;
    while(max>0)
    {
        nr++;
        x[nr]=a[p];
        max-=1;
        for(int i=p+1;i<n;i++)
            if(a[i]>a[p] && l[i]==max)
            {
                p=i;
                break;
            }
    }

    fprintf(fout,"%d\n",nr);
    for(int i=1;i<=nr;i++)
        fprintf(fout,"%d ",x[i]);

    fclose(fin);
    fclose(fout);
    return 0;
}