Cod sursa(job #779356)

Utilizator bratualexBratu Alexandru bratualex Data 17 august 2012 15:52:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int a[100000],best[100000],j,i,n,l,pbest,prec[100000],v[100000];
int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
    {
        fin>>a[i];
        best[i]=1;
        for ( j=i-1;j>0;j--)
        {
            if (a[i]>a[j])
                if(best[j]>=best[i])
                {

                    best[i]=1+best[j];
                    prec[i]=j;
                    if ( best[i]>l)
                    {
                        pbest=i;
                        l=best[i];
                    }
                }

        }
    }

    fout<<best[pbest]<<"\n";
    j=pbest;
    for(i=1;i<=best[pbest];i++)
    {
        v[i]=a[j];
        j=prec[j];
    }
    for(i=best[pbest];i>0;i--)
        fout<<v[i]<<" ";
    fout.close();
    return 0;
}