Cea mai lungă secvență crescatoare

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.

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