Cod sursa(job #1118932)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 24 februarie 2014 13:54:19
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
using namespace std;
int n,a[100002],i,j,b[100002],vmax,lmax,pmax;
int main()
{
    fstream fin,fout;
    fin.open("scmax.in",ios::in);
    fout.open("scmax.out",ios::out);
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }

    for(i=n;i>=1;i--)
    {
        vmax=0;
        for(j=i+1;j<=n;j++)
        {
            if((a[i]<a[j])&&(b[j]>vmax))
            {
                vmax=b[j];
            }
        }
        b[i]=1+vmax;
        if(b[i]>lmax)
        {
            lmax=b[i];
            pmax=i;
        }
    }
    fout<<lmax<<"\n";
    fout<<a[pmax]<<" ";
    for(i=pmax+1;i<=n && lmax>1;i++)
    {
        if(a[pmax]<a[i] && b[i]==lmax-1)
        {
            fout<<a[i]<<" ";
            pmax=i;
            lmax--;
        }
    }
    fout.close();
    fin.close();
    return 0;
}