Cod sursa(job #1824764)

Utilizator tudortarniceruTudor Tarniceru tudortarniceru Data 8 decembrie 2016 13:26:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int MAXN = 100005;
int n;
int v[MAXN], s[MAXN], c[MAXN];
vector<int> q;
int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    for (int i = 1; i <= n; ++i) {
        int maxx = 0;
        for (int j = 1; j < i; ++j) {
            if (v[i] > v[j]) {
                maxx = max(maxx, s[j]);
            }

        }
        s[i] = maxx + 1;
    }
    int sol = 0;
    for (int i = 1; i <= n; ++i) {
        sol = max(sol, s[i]);
    }
    fout << sol << '\n';
    for (int i = n; i >= 1; --i) {
        if (s[i] == sol) {
            q.push_back(v[i]);
            sol--;
        }
    }
    for (int i = q.size() - 1; i >= 0; --i) {
        fout << q[i] << ' ';
    }
    return 0;
}