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

În această lecție abordăm o aplicație tipică pentru secvențele dintr-un șir.

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;
}

DS

Autorul acestei lecții

Dominic Satnoianu

Această lecție a fost redactată de către Dominic Satnoianu.

© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.

Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te