Cod sursa(job #1663067)

Utilizator razvandRazvan Dumitru razvand Data 25 martie 2016 15:11:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>

using namespace std;

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

int v[100003];
int b[100003];
int o[100003];
int k;

deque<int> deq;

int main() {

    int n;

    int mxS = 0;
    int mxI = 0;

    in >> n;

    for(int i = 0; i < n; i++) {

        in >> v[i];

        b[i] = 1;

        for(int j = 0; j < i; j++) {

            if(v[i] > v[j]) {

                if(b[j]+1 > b[i]) {

                    b[i] = b[j]+1;
                    o[i] = j;

                    if(b[i] > mxS) {

                        mxS = b[i];
                        mxI = i;

                    }

                }

            }

        }

    }

    int i = mxI;
    stack<int> st;

    for(int j = 0; j < mxS; j++) {
        st.push(v[i]);
        i = o[i];
    }

    out << mxS << '\n';

    while(!st.empty())
        out << st.top() << " ", st.pop();

    int poz = 0;

    return 0;
}