Cod sursa(job #1645394)

Utilizator serbanSlincu Serban serban Data 10 martie 2016 12:12:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;

int a[100005];
int lis[100005];
int t[100005];

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

void afis(int i) {
    if(i) {
        afis(t[i]);
        g << a[i] << " ";
    }
}

int main()
{
    int n, m = 0, p; f >> n;
    for(int i = 1; i <= n; i ++) f >> a[i];
    lis[1] = 1;
    for(int i = 2; i <= n; i ++) {
        int mx = 0, poz = 0;
        for(int j = 1; j < i; j ++) {
            if(a[j] < a[i] && mx < lis[j]) mx = lis[j], poz = j;
        }
        lis[i] = mx + 1;
        t[i] = poz;
        if(lis[i] > m) m = lis[i], p = i;
    }
    g << m << "\n";
    afis(p); g << "\n";
    return 0;
}