Cod sursa(job #1666176)

Utilizator GeorginskyGeorge Georginsky Data 27 martie 2016 18:56:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MXN 100005
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int main(){
    int n, i, j, a[MXN], b[MXN], mx, pos;
    in>>n;
    b[0]=0;
    for(i=1; i<=n; i++){
        in>>a[i];
        b[i]=1;
    }
    mx=0;
    for(i=2; i<=n; i++){
        for(j=1; j<i; j++){
            if(a[j]<a[i]){
                b[i]=max(b[i], b[j]+1);
                if(b[i]>mx){
                    mx=b[i];
                    pos=i;
                }
            }
        }
    }
    int val=mx-1;
    i=pos-1;
    int last=pos;
    vector<int> x;
    x.push_back(a[pos]);
    while(val>0){
        while(b[i]!=val||a[i]>=a[last]){
            i--;
        }
        last=i;
        x.push_back(a[i]);
        val--;
    }
    out<<mx<<"\n";
    for(i=x.size()-1; i>=0; i--){
        out<<x[i]<<" ";
    }
    return 0;
}