Cod sursa(job #1086563)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 18 ianuarie 2014 12:26:35
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<vector>
 
#define NMAX 100007
 
using namespace std;
 
vector<int> p, q, sol;
int a[NMAX];
int n, poz;
 
int main(){
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    q.push_back(a[1]);
    p.push_back(0);
    for(int i = 2; i <= n; ++ i){
        vector<int>::iterator it = lower_bound(q.begin(), q.end(), a[i]);
        poz = (it - q.begin());
        if(it == q.end())
            q.push_back(a[i]);
        else
            *it = a[i];
        p.push_back(poz);
    }
    printf("%d\n", q.size());
    int Max = q.size() - 1;
    for(int i = n - 1; i >= 0; -- i)
        if(Max == p[i])
            if(sol.size() != 0 && sol[sol.size() - 1] > a[i + 1]){
                sol.push_back(a[i + 1]);
                -- Max;
            }
            else
                if(sol.size() == 0){
                    sol.push_back(a[i + 1]);
                    -- Max;
                }
    for(int i = sol.size() - 1; i >= 0; -- i)
        printf("%d ", sol[i]);
    return 0;
}