Cod sursa(job #1737464)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 4 august 2016 10:32:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#define DIM 100001
using namespace std;
int i,n,v[DIM],l[DIM],t[DIM],sol[DIM],j,p,maxim,k;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    n++;
    v[n] = 2000000001;
    l[1] = 1;
    for (i=2;i<=n;i++){
        maxim = 0;
        for (j=i-1;j>=1;j--){
            if (v[j] < v[i]){
                if (l[j] > maxim) {
                    maxim = l[j];
                    p = j;
                }
            }
        }
        l[i] = maxim + 1;
        if (maxim != 0)
            t[i] = p;
    }

    fout<<l[n]-1<<"\n";
    p = n;
    while (p!=0) {
        sol[++k] = v[p];
        p = t[p];
    }

    for (i=k;i>=2;i--)
        fout<<sol[i]<<" ";


    return 0;
}