Cod sursa(job #1090048)

Utilizator manutrutaEmanuel Truta manutruta Data 22 ianuarie 2014 11:56:31
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
using namespace std;

#define MAXN 100005

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

int n;
int a[MAXN];
int dist[MAXN];
int prev[MAXN];

void remake(int nd) {
    if (nd == prev[nd]) {
        return;
    }
    remake(prev[nd]);
    g << a[nd] << ' ';
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> a[i];
    }

    a[0] = 0;
    dist[0] = 0;
    for (int i = 1; i <= n; i++) {
        dist[i] = 0;
        for (int j = 0; j < i; j++) {
            if (dist[i] <= dist[j] && a[j] < a[i]) {
                dist[i] = dist[j] + 1;
                prev[i] = j;
            }
        }
    }

    int mx = 0, p = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > mx) {
            mx = dist[i];
            p = i;
        }
    }

    g << mx << endl;
    remake(p);
    return 0;
}