Cod sursa(job #1929823)

Utilizator Lungu007Lungu Ionut Lungu007 Data 18 martie 2017 10:36:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#define NMAX 100002
#define INF 2000000002
using namespace std;

int a[NMAX],d[NMAX],pre[NMAX],n;

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

int main()
{
    in >> n;
    for(int i=1;i<=n;i++) {
        in >> a[i];
        d[i] = 1;
    }
    d[n] = 1;
    for(int i=n-1;i>0;i--) {
        for(int j=i+1;j<=n;j++) {
            if(a[i] < a[j]) {
                if(d[i] < d[j]+1) {
                    d[i] = d[j]+1;
                    pre[i] = j;
                }
            }
        }
    }
    int contor = 0, poz = 0;
    for(int i=1;i<=n;i++) {
        if(d[i]> contor) {
            contor = d[i];
            poz = i;
        }
    }
    out << contor << '\n';
    for(int i=poz;i!=0;i = pre[i]) {
        out << a[i] << " ";
    }
    return 0;
}