Cod sursa(job #1896478)

Utilizator BlackREzRadut Alexandru Catalin BlackREz Data 28 februarie 2017 18:34:27
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>

using namespace std;

FILE* f;
FILE* g;
int n,m,a[100000],b[100000],prev[100000];
void read(){
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d",&a[i]);
}
int searchmax(int j,int x){
    int maxb=0,maxi=0;
    for(int i=j;i>=2;i--)
        if(x>a[i] && b[i]>maxb){
            maxb=b[i];
            maxi=i;
        }
    prev[j]=maxi;
    return maxb+1;
}
void output(int i,int maxim){
    if(maxim==0) return;
    output(prev[i],maxim-1);
    fprintf(g,"%d ",a[i]);
}
void solve(){
    for(int i=2;i<=n;i++)
        b[i]=searchmax(i,a[i]);

    int maxim=0,maximi;
    for(int i=n;i>=1;i--){
        if(b[i]>maxim) {
                maximi=i;
                maxim=b[i];
        }
    }
    fprintf(g,"%d \n",maxim);
    int i=maximi;
    output(i,maxim);
}
int main()
{
    f=fopen("scmax.in","r");
    g=fopen("scmax.out","w");
    b[1]=1;
    read();
    solve();
    return 0;
}