Cod sursa(job #677105)

Utilizator handz.FMI Andrei Tanasescu handz. Data 9 februarie 2012 21:04:45
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#define maxN 100005
#define minus_inf -2000000005
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

long n,L[maxN],v[maxN];
void read()
{
    int i;
    f>>n;
    for(i=1; i<=n ;i++)
    {
        f>>v[i];
        L[i]=0;
    }
}

void det_lmax()
{
    int i,k;
    L[n]=1;
    for(k=n-1; k>=1 ;k--)
    {
        L[k]=1;
        i=k;
        do
        {
            i++;
        }while(v[k]>v[i] && i<n);
        if(v[k]<=v[i])
            L[k]=L[i]+1;
    }
}

void print()
{
    int i,imax=0;
    long max,Lmax,d;
    max=minus_inf;
    for(i=1; i<=n ;i++)
        if(L[i]>max)
        {
            max=L[i];
            imax=i;
        }
    Lmax=max;
    g<<Lmax<<"\n";
    d=v[imax];
    for(i=imax; i<=n ;i++)
        if(v[i]>=d)
        {
            d=v[i];
            g<<d<<" ";
        }
}

int main()
{
    read();
    det_lmax();
    print();
    return 0;
}