Cod sursa(job #760876)

Utilizator alexclpAlexandru Clapa alexclp Data 23 iunie 2012 13:18:05
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>

using namespace std;

const int N = 100005;

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

int best[N], poz[N], v[N];

void sir(int p)
{
    if(p==0) return;
    sir(poz[p]);
    out << v[p] << " ";
}

int main()
{

    int n;

    in >> n;

    for(int i=1;i<=n;i++)
        in >> v[i];

    best[1] = 1;
    for(int i=2;i<=n;i++) {
        best[i] = 0;
        for(int j=1;j<i;j++)
            if(v[j] < v[i] && best[j] > best[i]) {
                poz[i] = j;
                best[i] = best[j];
            }
            best[i] ++;
    }

    int pmax = 1;
    for(int i=2 ; i<=n ; i++)
        if(best[i] > best[pmax])
            pmax = i;

    out << best[pmax] << "\n";

    sir(pmax);

    return 0;
}