Cod sursa(job #1193245)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 31 mai 2014 12:44:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>

using namespace std;

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

const int nmax = 100001;
int v[nmax] , lung[nmax] , pred[nmax];

void afisare(int i)
{
    if(pred[i])
        afisare(pred[i]);

    out << v[i] << ' ';
}

int main()
{
    int n , i , j , maxim , imax;

    in >> n;

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

    maxim = 0;
    for(i = 1 ; i <= n ; i++)
    {
        lung[i] = 0;

        for(j = 1 ; j < i ; j++)
            if(v[j] < v[i])
                if(lung[j] > lung[i])
                {
                    lung[i] = lung[j];
                    pred[i] = j;
                }

        lung[i]++;
        if(lung[i] > maxim)
        {
            maxim = lung[i];
            imax = i;
        }
    }

    out << maxim << '\n';

    afisare(imax);

    out << '\n';
    return 0;
}