Cod sursa(job #1047372)

Utilizator bogdan9183Bogdan Cionca bogdan9183 Data 4 decembrie 2013 12:11:07
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int n, v[100000], Lmax[100000], urm[100000], maxL;

void functie ()
{   int i, j, m, p;
    Lmax[n]=1;
    urm[n]=0;
    maxL=1;
    for (i=n-1; i>=1; i--)
    {
        m=0;
        for (j=i+1; j<=n; j++)
            if (v[i]<=v[j])
                if (m<Lmax[j])
                {
                    m=Lmax[j];
                    urm[i]=j;
                }

        Lmax[i]=m+1;
        maxL= max (maxL, Lmax[i]);
    }
}

int main()
{
    f>>n;
    for (int i=1; i<=n; i++)
        f>>v[i];

    functie ();
    g<<maxL<<'\n';
    for (int i=1; i<=n; i++)
        if (Lmax[i]==maxL)
        {
            int ind=i;
            while (ind!=0)
            {
                g<<v[ind]<<" ";
                ind=urm[ind];
            }
        break;
        }

    return 0;
}