Cod sursa(job #984010)

Utilizator daniel.amarieiDaniel Amariei daniel.amariei Data 13 august 2013 11:31:38
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#define MAXSIZE 100001

int N;
long a[MAXSIZE];
int best[MAXSIZE], pre[MAXSIZE];

int index_of_max(int i)
{
    int j;
    int max = 0;
    for (j = 1; j < i; ++j)
        if (a[j] < a[i] && best[j] > best[max])
            max = j;

    return max;
}

void print_solution(int i)
{
    if (pre[i] == 0)
    {
        printf("%ld", a[i]);
    } 
    else
    {
        print_solution(pre[i]);
        printf("% ld", a[i]);        
    }
}

int main()
{
    int i, j, max;
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf("%ld", &a[i]);

    for (i = 1; i <= N; ++i) 
    {
        j =  index_of_max(i);

        if(j == 0)
            best[i] = 1;
        else 
            best[i] = 1 + best[j];

        pre[i] = j;
    }

    for (i = 1; i <= N; ++i)
        if (best[i] > best[max])
            max = i;
    
    printf("%d\n", best[max]);
    print_solution(max);

    return 0;
}