Cod sursa(job #813275)

Utilizator TheShadowsAlexandru Cristian TheShadows Data 15 noiembrie 2012 08:59:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<cstdio>
using namespace std;
int l[100002], a[100002];
int makeFreq(int x){
    int pos, max, cmax=0; l[x]=1;
    for(int i=x-1; i>=1; --i){
        max=0;
        for(int j=i+1; j<=x; ++j)
            if(l[j]>max&&a[i]<a[j])
                max=l[j];
        l[i]=max+1;
        if(l[i]>cmax){
           cmax=l[i]; pos=i;
        }
    }
    return pos;
}
void printSolution(FILE *out, int start){
    int i, current=l[start];
    fprintf(out, "%d\n", l[start]);
    while(l[start]>1){
        fprintf(out, "%d ", a[start]);
        --current;
        for(i=start+1; l[i]!=current; ++i);
        start=i;
    }
    fprintf(out, "%d ", a[start]);
}
int main(){
    FILE *in=fopen("scmax.in","r"), *out=fopen("scmax.out","w");
    int n;
    fscanf(in,"%d",&n);
    for(int i=1; i<=n; ++i)
       fscanf(in, "%d", &a[i]);
    printSolution(out, makeFreq(n));
    return 0;
}