Cod sursa(job #1750133)

Utilizator LaurIleIle Laurentiu Daniel LaurIle Data 29 august 2016 17:14:32
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100000], l[100000], poz[100000], n;

void citesc()
{
    f >> n;
    for(int i=1; i<=n; i++)
        f >> a[i];
}

void rezolv()
{
    int i,j;
    l[n]=1; poz[n]=-1;
    for(i=n-1; i>0; i--)
    {
        l[i]=1; poz[i]=-1;
        for(j=i+1; j<=n; j++)
        {
            if(a[i]<=a[j] && l[i]<1+l[j])
            {
                l[i]=1+l[j]; poz[i]=j;
            }
        }
    }
 /*   for(i=1;i<=n;i++) cout<<l[i]<<" ";
    cout<<endl<<endl;
    for(i=1;i<=n;i++) cout<<poz[i]<<" ";
    cout<<endl<<endl; */
}

void afisez()
{
    int i, maxim=l[1], pozmax=1;
    for(i=2; i<=n; i++)
        if(maxim<l[i])
    {
        maxim=l[i];
        pozmax=i;
    }
    g<<maxim<<endl;
    for(i=pozmax; i!=-1; i=poz[i]) g<<a[i]<<" ";

}

int main()
{
    citesc();
    rezolv();
    afisez();
    return 0;
}