Cod sursa(job #1785972)

Utilizator OvidelwHolca Ovidiu Ovidelw Data 22 octombrie 2016 10:33:52
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

int a[100001], n, b[100001], pozitie[1000003];

int main()
{
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);
    scanf ("%d", &n);
    for (int i = 0; i < n; i++)
        scanf ("%d", &a[i]);
    int maxi = 1, p = n - 1;
    b[n - 1] = 1;
    pozitie[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--)
    {
        b[i] = 1;
        pozitie[i] = -1;
        for (int j = i + 1; j < n; j++)
            if (a[i] < a[j] && b[i] < b[j] + 1)
            {
                b[i] = b[j] + 1;
                pozitie[i] = j;
                if (b[i] > maxi)
                {
                    maxi = b[i];}
                    p = i;
                }
    }
    printf ("%d\n", maxi);
    int k = p;
    while (k != -1)
    {
        printf ("%d ", a[k]);
        k = pozitie[k];
    }
    return 0;
}