Cod sursa(job #3196190)

Utilizator rapidu36Victor Manz rapidu36 Data 23 ianuarie 2024 09:09:46
Problema Subsir crescator maximal Scor 70
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100000

FILE *in,*out;

int v[N+1],l_max[N+1];

void refac_subsirul(int p, int val, int lung)
{
    if(lung == 0)
    {
        return;
    }
    if(v[p] <= val && l_max[p] == lung)
    {
        refac_subsirul(p-1, v[p]-1,lung-1);
        fprintf(out,"%d ",v[p]);
    }
    else
    {
        refac_subsirul(p-1, val, lung);
    }
}

int max(int a, int b)
{
    if(a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}

int main()
{
    in = fopen("scmax.in","r");
    out = fopen("scmax.out","w");
    int n,i_max=0;
    fscanf(in, "%d",&n);
    for(int i = 0; i < n; i++)
    {
        fscanf(in, "%d", &v[i]);
        int len = 0;
        for(int j = 0; j < i; j++)
        {
            if(v[j] < v[i])
            {
                len = max(len,l_max[j]);
            }
        }
        l_max[i] = len+1;
        if(l_max[i] > l_max[i_max])
        {
            i_max = i;
        }
    }
    fprintf(out,"%d\n",l_max[i_max]);
    refac_subsirul(i_max,v[i_max],l_max[i_max]);
    fclose(in);
    fclose(out);
    return 0;
}