Cod sursa(job #705314)

Utilizator informatician28Andrei Dinu informatician28 Data 4 martie 2012 00:36:28
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#define DIM 100001
using namespace std;

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

int Best[DIM], Pre[DIM];
int N, maxim, poz;
long long V[DIM];

void rebuild(int pozitie)
{
    if( Pre[pozitie] == 0 )
       {
           out << V[pozitie] << " ";
           return;
    }
    else {
        rebuild( Pre[pozitie] );
        out << V[pozitie] << " ";
    }
}
int main()
{
    int i, j;
    in >> N;
    for(i = 1; i <= N; i++)
        in >> V[i];
    
    Best[1] = 1; // lungimea unui subsir crescator care se termina in 1
    for(i = 2; i <= N; i++)
        {
            maxim = 0;
            for(j = 1; j < i; j++)
            if( V[j] < V[i] )
                if( Best[j] > maxim )
                    {
                        maxim = Best[j];
                        poz = j;
                    }
            Best[i] = 1 + maxim;
            Pre[i] = poz;
        }
    maxim = 0;
    for(i = 1; i <= N; i++)
        if( Best[i] > maxim )
            maxim = Best[i], poz = i;
    out << maxim << '\n';
    rebuild(poz);
}