Cod sursa(job #2173873)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 16 martie 2018 09:19:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <cstdio>
#define NMAX 100005

using namespace std;

int N, v[NMAX], dp[NMAX], maxim, pozMax;

void read(){
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        scanf("%d ", &v[i]);
    }
}

int maxi(int poz) {
    int s = 0;
    for(int i = poz + 1; i < N; ++i) {
        if(dp[i] > s && v[i] > v[poz]) {
            s = dp[i];
        }
    }
    return s;
}

void gasireLungMaxima() {
    maxim = 1;
    pozMax = N - 1;
    dp[N - 1] = 1;
    for(int i = N - 2; i >= 0; --i) {
        dp[i] = 1 + maxi(i);
        if(dp[i] > maxim) {
            maxim = dp[i];
            pozMax = i;
        }
    }
}

void print() {
    printf("%d\n", maxim);
    printf("%d ", v[pozMax]);
    for(int i = pozMax; i < N; ++i) {
        if(dp[i] + 1 == dp[pozMax] && v[i] > v[pozMax]) {
            printf("%d ", v[i]);
            pozMax = i;
        }
    }
}

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    read();
    gasireLungMaxima();
    print();
    return 0;
}