Cod sursa(job #3315327)

Utilizator zionlyismAdobroaiei David zionlyism Data 13 octombrie 2025 20:40:06
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>

#define NMAX 100002

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int i, j, n, a[NMAX];
int maxim, pozmax;
int dp[NMAX];     //dp[i] = lg maxima a unui subsir care incepe la pozitia i

int urmatorul[NMAX]; //pentru afisare. daca urmatorul[i] = 0 atunci sunt la cel mai mare element din acel subsir

int main()
{
    fin>>n;
    for(i = 1; i <= n; i++)
        fin>>a[i];
    dp[n] = 1;
    for(i = n - 1; i > 0; i--)
       {
        maxim = 0;
        for(j = i + 1; j <= n; j++)
            if(a[i] < a[j]) //conditie subsir crescator
              if(maxim < dp[j])
                {
                 maxim = dp[j];
                 urmatorul[i] = j;
                }
        dp[i] = maxim + 1; //chiar si daca sunt in cazul incare nu pot atasa a[i] la un subsir, maxim + 1 = 1 deci voi incepe un subsir pe acea pozitie
       }
    //caut cel mai lung subsir
    for(i = 1, maxim = 0; i <= n; i++) //voi refolosi variabila maxim (dar nu pentru acelasi scop)
        if(maxim < dp[i])
           {
            maxim = dp[i];
            pozmax = i;
           }
    fout<<maxim<<'\n'; //lungime subsir maxim
    while(pozmax)
        {
         fout<<pozmax<<' ';
         pozmax = urmatorul[pozmax];
        }
    return 0;
}