Cod sursa(job #1429704)

Utilizator alexandru.jercaianuJercaianu Alexandru alexandru.jercaianu Data 6 mai 2015 22:55:10
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<limits>
using namespace std;

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

typedef long long ll;

int main()
{  
    vector<ll> sol;
    vector<ll> v;
    int N;
    fin >> N;
    vector<ll> d(N, 1);
    vector<ll> p(N, -1);
    for (int i = 0; i < N; i++) {
        ll aux;
        fin >> aux;
        v.push_back(aux);
    }
    ll current = v[0];
    d[0] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 0 ; j < i; j++) {
            d[i] = max(d[i], d[j]);
            if (v[i] > v[j]) {
                if (d[i] < d[j] + 1) {
                    d[i] = d[j] + 1;
                    p[i] = j;
                }
            }
        }
    }
    int aux;
    int max = 0;
    for (int i= 0; i < N; i++) {
       if (d[i] > d[max]) {
            max = i;
       }
    }
    fout << d[max] << endl;
    aux = max;
    while (aux != -1) {
        sol.push_back(v[aux]);
        aux = p[aux];
    }
    for (int i = sol.size() - 1; i >= 0; i--) {
        fout << sol[i] << " ";
    }
    
    
    
}