Cea mai lungă secvență de elemente crescătoare în C++

Dându-se un șir de numere, să se determine cea mai lungă secvență de elemente consecutive, cu valori strict crescătoare.

Exemplu: Pentru șirul [1, 6, 2, 3, 9, 11, 9, 10], secvența de lungime maximă cu elemente crescătoare este [2, 3, 9, 11], care începe de pe poziția 3 și se termină pe poziția 6.

Explicarea algoritmului

Vom ține contoare pentru secvența maximă până într-un punct curent, precum și contoare pentru secvența curentă. Dacă elementul curent este mai mare decât elementul anterior, atunci incrementăm lungimea secvenței curente. Altfel, formăm o nouă secvență de lungime 1, dar nu înainte de a verifica dacă secvența este mai mare decât cea maximă până în acel punct.

Rezolvare în C++

Iată rezolvarea problemei:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim valorile
    int n, a[101];
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    //Căutăm secvența cu elemente crescătoare
    int startMax = 0, lungMax = 0, startCrt = 1, lungCrt = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > a[i - 1]) {
            lungCrt++;
        } else {
            if(lungCrt > lungMax) { //Verificăm dacă secvența curentă este maximă
                startMax = startCrt;
                lungMax = lungCrt - 1;
            }
            startCrt = i;
            lungCrt = 1;
        }
    }

    //Afișăm secvența maximă
    for(int i = startMax; i <= startMax + lungMax; i++) {
        cout << a[i] << " ";
    }
    return 0;
}