Cod sursa(job #1782421)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 18 octombrie 2016 09:18:15
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>

using namespace std;

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

long long N, poz, op[100003], ult[100003], a[100003], MAX;
int main()
{
    f >> N;
    for(int i = 1; i <= N; i++) f >> a[i];
    for(int i = N; i >= 1; i--) {
        op[poz] = 1;
        ult[i] = -10;
        for(int j = i+1; j <= N; j++) {
            if(a[i] < a[j] && op[i] < op[j] + 1)
                op[i] = op[j] + 1, ult[i] = j;
            if(op[i] > MAX) MAX = op[i], poz = i;
        }
    }
    g << MAX << "\n";
    for(int i = poz; i >= 0; i = ult[i]) g << a[i] << " ";

    g << "\n";
    return 0;
}