Cod sursa(job #923951)

Utilizator DarkyAngelDarky Angel DarkyAngel Data 23 martie 2013 23:27:07
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

long n,sir[100001],l[100001],u[100001];

void read(),solve();

int main() {
    read();
    solve();
}

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

void solve() {
    long i,j,max,maxi,tmax,tmaxi;
    l[n]=1;
    u[n]=0;
    tmax=tmaxi=0;
    for(i=n-1;i>0;i--) {
        max=maxi=0;
        for(j=i+1;j<=n;j++)
            if(l[j]>max&&sir[i]<sir[j])
               max=l[j],maxi=j;
        l[i]=1+max;
        u[i]=maxi;
        if(l[i]>tmax)
            tmax=l[i],tmaxi=u[i];
    }
    g<<tmax<<'\n';
    do {
        g<<sir[tmaxi]<<' ';
        tmaxi=u[tmaxi];
    } while (tmaxi);
    g.close();
}