Cod sursa(job #566401)

Utilizator undogSavu Victor Gabriel undog Data 28 martie 2011 22:23:00
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>

using namespace std;


int main(){
    int v[100000];
    int n;
    ifstream in("scmax.in");
    ofstream out("scma.out");
    int i,j,max;
    int sol[100000];

    in>>n;
    for(i=0;i<n;i++)
        in>>v[i];
    max=0;
    for(i=0;i<n;i++){
            sol[i]=0;
            for(j=0;j<i;j++)
                if(v[i]>v[j]&&sol[i]<sol[j])
                    sol[i]=sol[j];
            sol[i]++;
            if(max<sol[i])
                max = sol[i];
    }

    for(i=0;i<n;i++)
            if(sol[i]==max)
                break;
    int vct[100000];
    out<<max<<endl;
    max=0;
    vct[max++]=v[i];
    while(sol[i]>1){
        for(j=0;j<i;j++)
                if(v[i]>v[j]&&sol[j]+1==sol[i])
                    break;
        i=j;
        vct[max++]=v[i];
    }

    for(i=max-1;i>=0;i--)
        out<<vct[i]<<" ";
    out<<endl;
    return 0;
}