Cod sursa(job #808329)

Utilizator DisturbedTeuca Sergiu Disturbed Data 6 noiembrie 2012 17:24:05
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    long n,maxx,imax;
    int i,j;
    long a[100000],u[100000],l[100000];
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i];
    for(i=n-1;i>=1;--i)
    {
        maxx=0;imax=0;
        for(j=i+1;j<=n;++j)
            if ((l[j]>maxx)&&(a[i]<=a[j]))
            {
                maxx=l[j];
                imax=j;
            }
        l[i]=1+maxx;
        u[i]=imax;
    }
    maxx=l[1]; imax=1;
    for(j=2;j<=n;++j)
        if (l[j]>maxx)
        {
            maxx=l[j];
            imax=j;
        }
   g<<maxx<<"\n";
   while (imax!=0)
   {
       g<<a[imax]<<" ";
       imax=u[imax];
   }
   g.close();
   return 0;
}