Cod sursa(job #892439)

Utilizator alexandrul_21Niculescu Mihai alexandrul_21 Data 26 februarie 2013 09:33:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <stdio.h>
using namespace std;
#define MAX_N 100000
int V[MAX_N+5],S[MAX_N+5];
int N,Max,F;
void Read(){
    freopen("scmax.in","r",stdin);
    scanf("%d\n",&N);
    int i,n=N;
    for(i=1;i<=n;i++){
        scanf("%d ",&V[i]);
    }
    fclose(stdin);
}
void PD(){
    int max,i,j,n=N;
    S[n]=1;
    for(i=n-1;i>0;i--){
        max=0;
        for(j=i+1;j<=n;j++){
            if(V[i]<V[j]&&max<S[j]){
                max=S[j];
            }
        }
        S[i]=max+1;
        if(Max<S[i]){
            F=i;
            Max=S[i];
        }
//        printf("%d %d\n",i,S[i]);
    }
}
void Write(){
    int i;
    ofstream fout("scmax.out");
    fout<<Max<<'\n';
    for(i=F;i<=N;i++){
        if(S[i]==Max){
            fout<<V[i]<<' ';
            Max--;
            if(Max==0)
                return;
        }
    }
    fout.close();
}
int main()
{
    Read();
    PD();
    Write();
    return 0;
}