Cod sursa(job #2215729)

Utilizator georgiuadrianadrian georgiuadrian Data 23 iunie 2018 13:14:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>

using namespace std;

int a[100005];
int poz[100005];
int best[100005];
int main(void)
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    int n;
    int p;
    int maxim = 0;

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

    best[n] = 1;
    poz[n] = -1;
    for (int i = n - 1; i; --i)
    {
        best[i] = 1;
        poz[i] = -1;
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] < a[j] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                poz[i] = j;
                if (best[i] > maxim)
                {
                    maxim = best[i];
                    p = i;
                }

            }
        }
    }

    printf("%d\n", maxim);
    while (p != -1)
    {
        printf("%d ", a[p]);
        p = poz[p];
    }

    fclose(stdin);
    fclose(stdout);
}