Cod sursa(job #858698)

Utilizator tsubyRazvan Idomir tsuby Data 19 ianuarie 2013 11:24:23
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>

using namespace std;

int n, sir[100000], length[100000], urm[100000];

void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d ", &sir[i]);
}

void lungime()
{
    length[n] = 1;
    urm[n] = -1;
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
            if(length[i] < 1+length[j] && sir[j] > sir[i])
            {
                length[i] = length[j] + 1;
                urm[i] = j;
            }
        if(length[i] == 0)
        {
            length[i] = 1;
            urm[i] = -1;
        }
    }
}

int maxim_length()
{
    int max = -1;
    for(int i=1;i<=n;i++)
        if(max < length[i])
            max = i;
    return max;
}

void afisare()
{
    int ok = 0;
    int p = maxim_length();
    printf("%d\n", length[p]);
    for(int i=p;i!=-1;)
    {
        printf("%d ",sir[i]);
        i = urm[i];
    }
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    citire();
    lungime();
    afisare();
    return 0;
}