Cod sursa(job #1609398)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 22 februarie 2016 19:42:44
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int N_max = 100002;

int v[N_max];

int lung[N_max]; // lung[i] == LUNGIMEA CELUI MAI LUNG SUBSIR CRESCATOR CARE SE TERMINA PE POZ i

int pred[N_max];

int L_max;

int N;

void calcul(int x)
{
    if(x == 0) return;

    calcul(pred[x]);

    out << v[x] << " ";
}

int main()
{
    int i, j, poz;

    in >> N;

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

    lung[1] = 1;
    pred[1] = 0;

    L_max = lung[1];
    poz = 1;

    for(i = 2; i <= N; i++)
    {
        lung[i] = 0;
        pred[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(L_max < lung[i])
        {
            L_max = lung[i];

            poz = i;
        }
    }

    out << L_max << '\n';

    calcul(poz);

    return 0;
}