Cod sursa(job #1619274)

Utilizator Victor24Vasiesiu Victor Victor24 Data 28 februarie 2016 14:39:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <cstring>
using namespace std;

int n, i, j, a[100001], lu[100001],pa[100001], inc, ma;

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

int main () {

f>>n;

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

for (i=1; i<=n; i++) {
    lu[i]=1;
}

pa[n]=0;

for (i=n-1; i>=1; i--) {
    for (j=n; j>i; j--) {
        if (a[i]<a[j]&&lu[j]+1>=lu[i]) {
            lu[i]=lu[j]+1;
            if (lu[j]+1>=ma) {ma=lu[j]+1; inc=i;}
            pa[i]=j;
        }
    }
}

g<<ma<<'\n';

for (i=1; i<=ma; i++) {
    g<<a[inc]<<" ";
    inc=pa[inc];
}

return 0;
}