Cod sursa(job #664496)

Utilizator stefangab95Muscalu Stefan Gabriel stefangab95 Data 20 ianuarie 2012 10:25:00
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>

using namespace std;
int n,i,L[100000],mxx,mx,k,t;
long long v[100000];
FILE * fin=fopen("scmax.in","r");
FILE * fout=fopen("scmax.out","w");
int main(){

    fscanf(fin,"%d",&n);

    for(i=1;i<=n;i++) fscanf(fin,"%lld",&v[i]);
    L[n]=1; //subsir maxim de lung 1

    for(k=n-1;k>0;k--)
    {
        mx=0;
        for(i=k+1;i<=n;i++)
            if(v[i]>=v[k] && L[i]>mx)
                mx=L[i];
        L[k]=mx+1;

        if(L[k]>mxx)
        {
            mxx=L[k];
            t=k;
        }
   }

    fprintf(fout,"%d\n",mxx);
    //afisarea subsirului
    fprintf(fout,"%lld ",v[t]);
    for(i=t+1;i<=n;i++)
        if ((v[i]>=v[t]) && (L[i]==mxx-1))
            {
                fprintf(fout,"%lld ",v[i]);
                mxx--;
            }

return 0;

}