Cod sursa(job #2989993)

Utilizator AndreiTitus10Andrei Titus AndreiTitus10 Data 7 martie 2023 13:09:37
Problema Subsir crescator maximal Scor 70
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <stdlib.h>

int main()
{

    FILE *fi=fopen("scmax.in","r");
    FILE *fo=fopen("scmax.out","w");
    const int maxn = 1e5 + 5;
    int V[maxn], X[maxn], Ante[maxn];
    int n, i, j, maxx, p;
    fscanf(fi,"%d",&n);
    for (i = 1; i <= n; i++)
        fscanf(fi,"%d",&V[i]);
    X[n] = 1;
    Ante[n] = -1;
    maxx = 1;
    p = n;
    for (i = n - 1; i; i--)
    {
        X[i] = 1;
        Ante[i] = -1;
        for (j = i + 1; j <= n; j++)
        {
            if (X[j] + 1 > X[i] && V[j] > V[i])
            {
                X[i] = X[j] + 1;
                Ante[i] = j;
            }
            if (X[i] > maxx)
            {
                maxx = X[i];
                p = i;
            }
        }
    }
    fprintf(fo,"%d\n",maxx);
    i = p;
    while (i != -1)
    {
        fprintf(fo,"%d ",V[i]);
        i = Ante[i];
    }

    return 0;

}