Cod sursa(job #1429938)

Utilizator cruceru_vlad_ionut_321CACruceru Vlad - Ionut 321CA cruceru_vlad_ionut_321CA Data 7 mai 2015 16:52:08
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>

using namespace std;

long long vec[100000];
long lungimi[100000];
long tati[100000];

int main()
{
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    long n;
    f >> n;
    for(long i = 0; i < n; i++)
        f >> vec[i];
    long lung = 0;
    long idx = -1;
    for(long i = n - 1; i >= 0; i--)
    {
        lungimi[i] = 1;
        for(long j = i + 1; j < n; j++)
            if((vec[i] < vec[j]) && (lungimi[i] < lungimi[j] + 1))
            {
                lungimi[i] = lungimi[j] + 1;
                tati[i] = j;
            }
        if(lung < lungimi[i])
        {
            lung = lungimi[i];
            idx = i;
        }
    }

    g << lung <<endl;
    do
    {
        g << vec[idx] << " ";
        idx = tati[idx];
    }   
    while(idx != 0);
    g << '\n';

    f.close();
    g.close();

    return 0;
}