Cerinţa

Se dă un șir cu n elemente, numere naturale. Determinați un cel mai lung subșir crescător al șirului.

Date de intrare

Fişierul de intrare sclm.in conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii, reprezentând elementele șirului.

Date de ieşire

Fişierul de ieşire sclm.out va conţine pe prima linie numărul L, reprezentând lungimea maximă a unui subșir crescător. A doua linie va conține L numere cu valori între 1 și n, ordonate crescător, reprezentând indicii elementelor din șirul dat care dau subșirul crescător de lungime maximă.

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fişierului de intrare vor fi cel mult egali cu 1.000.000
• orice șir de indici care duce la subșir crescător de lungime maximă este corectă

Exemplu

sclm.in

10
5 10 7 4 5 8 9 8 10 2 

sclm.out

5
1 3 6 7 9 

Explicație

Elementele șirului care corespund acestor indici sunt: 5 7 8 9 10.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("sclm.in");
ofstream cout("sclm.out");

int n , a[1002] , L[1002] , P[1002] , p , l , pmax , lmax;

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    for(int i = n ; i >= 1 ; i--)
    {
        p = i;
        l = 0;
        for(int j = i + 1 ; j <= n ; j++)
            if(a[i] <= a[j] && L[j] > l)
            {
                l = L[j];
                p = j;
            }
        L[i] = l + 1;
        P[i] = p;
        if(L[i] > lmax)
        {
            lmax = L[i];
            pmax = i;
        }
    }
    /*for(int i = 1 ; i <= n ; i++)
        cout << L[i] << " ";
    cout << '\n';
    for(int i = 1 ; i <= n ; i++)
        cout << P[i] << " ";*/
    cout << lmax << '\n';
    p = pmax;

    while(p != P[p])
    {
        cout << p << " ";
        p = P[p];
    }
    cout << p;
    return 0;
}