Cod sursa(job #1013601)

Utilizator CatalinaRaduCatalina Elena Radu CatalinaRadu Data 21 octombrie 2013 12:15:40
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g ("scmax.out");
long a [100001], best [100001], pre[100001],lmax,poz,n;

void citire()
{
    long i;
    f>>n;
    for (i=1;i<=n;i++)
        f>>a[i];
}

void sir ()
{
    long i, j;
    best[n]=1;
    pre[n]=-1;
    lmax=1; poz=n;
    for (i=n-1; i>=1;i--)
    {
        best[i]=1;
        for (j=i+1;j<=n;j++)
        if (a[i]<a[j] && best[i]<best[j]+1)
        {
            best[i]=best[j]+1;
            pre[i]=j;
            if (lmax<best[i])
            {
                lmax=best[i];
                poz=i;
            }
        }
        }
    }
void afisare ()
{
    long i;
    i=poz;
    while(i!=-1)
    {
     g<<a[i]<<" ";
     i=pre[i];
    }
}


int main()
{
    citire();
    sir();
    g<<lmax<<endl;
    afisare();
    return 0;
}