Cod sursa(job #358708)

Utilizator darkdudeAndrei Barsan darkdude Data 24 octombrie 2009 10:29:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream.h>
#define NMAX 100002

using namespace std;

int A[NMAX], L[NMAX], T[NMAX];

void afis(int imax)
{
    if(imax)
    {
        afis(T[imax]);
        cout<<A[imax]<<" ";
    }
}

int main()
{
    int i,j;

    int n, lmax, imax;

    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);

    cin>>n;
    for(i=1; i<=n; i++)
        cin>>A[i];

    L[1]=1;
    T[1]=0;

    for(i=2; i<=n; i++)
    {
        for(j=1, lmax = -1, imax = 0; j<=i-1; j++)
            if(L[j]>lmax && A[j]<A[i]) lmax = L[j], imax = j;

        if(lmax == -1)
            L[i] = 1, T[i] = 0;
        else
            L[i] = lmax + 1, T[i] = imax;
    }

    for(i=1, lmax = -1, imax = 0; i<=n; i++)
        if(L[i]>lmax) lmax = L[i], imax = i;


    cout<<L[imax]<<endl;
    afis(imax);

    return 0;
}