Cod sursa(job #1015901)

Utilizator c0rn1Goran Cornel c0rn1 Data 25 octombrie 2013 14:05:13
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, a[100000], L[100000], urm[100000], indx_max;

void citire()
{
    ifstream fin("scmax.in");
    fin>>n;
    for (int i=0; i<n; i++)
        fin>>a[i];
}

void rezolvare()
{
    L[n-1]=1;
    for (int i=n-2; i>=0; i--)
    {
        urm[i]=i;   /// retin pozitia maximului
                    /// din secventa
                    /// ______
                    /// i+1, n
        L[i]=0;
        for (int j=i+1; j<n; j++)
           if (a[i]<a[j] && L[urm[i]]<L[j])
                urm[i]=j;
        L[i]=L[urm[i]]+1;

        if (L[i]>L[indx_max])
            indx_max=i;
    }
}

void afisare()
{
    ofstream fout("scmax.out");
    fout<<L[indx_max]<<'\n';
    int i=indx_max;
    while(i!=urm[i])
    {
        fout<<a[i]<<' ';
        i=urm[i];
    }
    fout<<"\n";
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}