Cod sursa(job #3339422)

Utilizator Lascu_NicoleLascu Nicole Iraida Lascu_Nicole Data 8 februarie 2026 08:57:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>

using namespace std;

int v[100001], d[100001], t[100001];
int n, u, sol, p, maxi;

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

void drum (int u)
{
    if (u > 0)
    {
        drum (t[u]);
        cout << v[u] << " ";
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
     cin >> v[i];
     
    d[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int maxi = 0;
        for (int j = 1; j < i; j++)
         if ((v[j] < v[i]) && (d[j] > maxi))
         {
             maxi = d[j];
             p = j;
         }
         d[i] = maxi + 1;
         
         if (d[i] != 1) t[i] = p;// daca am un subsir cu m mult de 1 elem
          else t[i] = 0;
          
        if (d[i] > sol) {
            sol = d[i]; // actualizez lungimea maxima a unui subsir
            u = i;
        }
    }
    
    cout << sol << '\n';
    drum (u);

    return 0;
}