Cod sursa(job #1604795)

Utilizator georgen2George georgen2 Data 18 februarie 2016 16:39:49
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100],n,maxx[100],next[100],s[100];
int sub_max (int a[], int n)
{
    int i,j,l,incep;
    maxx[n]=1;
    next[n]=-1;
    for (i=n-1; i>=1; i--)
    {
        maxx[i]=1;
        next[i]=-1;
        for (j=i+1; j<=n; j++)
            if (a[i]<=a[j] && maxx[i]<=maxx[j])
            {
                maxx[i]=maxx[j]+1;
                next[i]=j;
            }
    }
    l=maxx[1];
    incep=1;
    for (i=2; i<=n; i++)
        if (l<maxx[i])
        {
            l=maxx[i];
            incep=i;
        }
    s[1]=a[incep];
    for (int i=2; i<=l; i++)
    {
        incep=next[incep];
        s[i]=a[incep];
    }
    return l;
}
int main()
{
    f>>n;
    for (int i=1; i<=n; i++)
        f>>a[i];
    int lmax=sub_max (a,n);
    g<<lmax<<'\n';
    for (int i=1; i<=lmax; i++)
        g<<s[i]<<" ";
        f.close();
        g.close();
    return 0;
}