Cod sursa(job #858678)

Utilizator tsubyRazvan Idomir tsuby Data 19 ianuarie 2013 10:28:18
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>

using namespace std;

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

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;j<=n;j++)
            if(length[i] < 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", 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;
}