Cod sursa(job #874351)

Utilizator RazzinnatorRazvan Brinzea Razzinnator Data 8 februarie 2013 11:01:12
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");

int main()
{
    int poz,max,i,j,n,v[100],l[100],succ[100],maxl=1,primpoz,pozcurent;
    f >> n;
    for(i=1;i<=n;i++)
    {
        f >> v[i];
    }

    succ[n] = 0;
    l[n] = 1;

    for(i=n-1;i>=1;i--)
    {
        max = 1;
        for(j=i+1;j<=n;j++)
        {
            if( v[i]<v[j] )
            {
                if( max <= l[j] )
                {
                    max = l[j]+1;
                    poz = j;
                }
            }
        }
        l[i] = max;
        if(l[i] > maxl)
        {
            maxl = l[i];
            primpoz = i;

        }
        if(max == 1)
        {
            succ[i] = 0;
        }
        else
        {
            succ[i] = poz;
        }
    }
    pozcurent = primpoz;

    g << maxl << '\n';

    for(i=1;i<=maxl;i++)
    {
        g << v[pozcurent] << ' ';
        pozcurent = succ[pozcurent];
    }
    g << '\n';
    f.close();
    g.close();
    return 0;
}