Cod sursa(job #2020902)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 12 septembrie 2017 08:26:06
Problema Subsir 2 Scor 14
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>

using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

const int nmax = 5005;
int i, j, n, a[nmax], b[nmax], c[nmax], max1;

int main() {
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];

    a[0] = 1e9;
    for (i = n; i >= 1; i--) {
        max1 = 0;
        for (j = i+1; j <= n; j++)
            if (a[i] < a[j] && max1 < b[j])
                max1 = b[j];

        for (j = i+1; j <= n; j++)
            if (b[j] == max1 && a[i] < a[j] && a[c[i]] > a[j])
                c[i] = j;
        b[i] = max1+1;
        if (max1==0) c[i] = n+1;
    }
    for (i = 1; i <= n; i++)
        if (max1 < b[i]) max1 = b[i];

    int min1 = 0;
    for (i = 1; i <= n; i++)
        if (max1 == b[i] && a[i] < a[min1])
            min1 = i;

    while (min1 <= n) {
        g << min1 << ' ';
        min1 = c[min1];
    }

}