Cod sursa(job #923980)

Utilizator DarkyAngelDarky Angel DarkyAngel Data 23 martie 2013 23:50:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 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;
    l[n]=1;
    u[n]=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;
    }
    max=l[1];
    maxi=1;
    for(i=2;i<=n;i++)
        if(l[i]>max)
            max=l[i],maxi=i;
    g<<max<<'\n';
    do {
        g<<sir[maxi]<<' ';
        maxi=u[maxi];
    } while (maxi);
    g.close();
}