Cod sursa(job #1001285)

Utilizator RusuRusu Daniel Rusu Data 24 septembrie 2013 20:05:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>

using namespace std;

//ifstream fin("scmax.in");
//ofstream fout("scmax.out");

inline int getInt() {
    int res = 0, pos = 1 ;
    char ch ;
    ch = getchar() ;
    for (;ch < '0' || ch > '9'; ch = getchar()) pos = (ch == '-' ? 0 : 1) ;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) res = res * 10 + (ch - '0') ;
    if (pos == 0) res *= -1 ;
    return res ;
}

struct element {
    int e, mx, nxt;
};

element v[100001];
int n, i, j, mx;

int main() {
    freopen("scmax.in", "r", stdin) ;
    freopen("scmax.out", "w", stdout) ;
    //fin >> n;
    n = getInt() ;
    for(i = 1;i <= n;i++) {
        //fin >> v[i].e;
        v[i].e = getInt() ;
    }
    mx = n;
    v[n].mx = 1;
    v[n].nxt = 0;
    for(i = n - 1;i > 0;i--) {
        v[i].nxt = 0;
        v[i].mx = 1;
        for(j = i + 1;j <= n;j++) {
            if(v[j].e > v[i].e && v[j].mx >= v[i].mx) {
                v[i].mx = v[j].mx + 1;
                v[i].nxt = j;
            }
        }
        if(v[mx].mx < v[i].mx) mx = i;
    }

    //fout << v[mx].mx << '\n';
    printf("%d\n", v[mx].mx) ;
    while(mx != 0) {
        printf("%d ", v[mx].e) ;
        //fout << v[mx].e << ' ';
        mx = v[mx].nxt;
    }

    //fin.close();
    //fout.close();

    return 0;
}