Cod sursa(job #1844110)

Utilizator mdiannnaMarusic Diana mdiannna Data 9 ianuarie 2017 19:06:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <stack>

using namespace std;
typedef long long ll;

int A[100001];
ll M[100001];
int Pred[100001];
int N;

void read(){
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> A[i];
}

void showSub(int maxi){
    stack<ll> S;

    int i = maxi;

    while(i > 0){
        S.push(A[i]);
        i = Pred[i];
    }
    while(!S.empty()){
        cout << S.top() << " ";
        S.pop();
    }
}

int main(){
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    read();

    M[0] = 0;
    M[1] = 1;
    Pred[1] = 0;

    ll maxim = 0;
    int max_pos = 0;
    int maxi = 1;

    for(int i=2; i<=N; i++){
        maxim = 0;
        max_pos = 0;
        for(int j=1; j<i; j++){
                if(A[j] < A[i] && M[j] > maxim){
                    maxim = M[j];
                    max_pos = j;
            }
        }
        if(maxim + 1 > M[maxi])
            maxi = i;
        Pred[i] = max_pos;
        M[i] = maxim + 1;

    }
    cout << M[maxi] << "\n";


    showSub(maxi);

	return 0;
}