Cod sursa(job #869501)

Utilizator PlatonPlaton Vlad Platon Data 1 februarie 2013 18:43:49
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>

long v[100000], l[100000],n, i, k, mx, maxi, pos;

using namespace std;

int main()
{
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    f>>n;
    for(i=1;i<=n;i++)
    f>>v[i];

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

    g<<maxi<<"\n";
    g<<v[pos]<<" ";
    for(i=1;i<=n;i++)
    {
        if (l[i]==maxi-1)
        {
            g<<v[i]<<" ";
            maxi--;
        }
    }
}