Zadanie 2. Napisz program, który wypisze najdłuższy spójny rosnący ciąg liczb całkowitych. Jeśli takich ciągów jest kilka, program powinien wypisać pierwszy.
W pierwszym wierszu jedna liczba n określająca ilość liczb w ciągu (n < 106).
W drugim wierszu n liczb całkowitych z przedziału [0..1000].
Szukany ciąg liczb.
Wejście
10
1 2 3 3 2 4 5 7 0 9
Wyjście
2 4 5 7
Rozwiązanie.
#include<iostream>
using namespace std;
int main()
{
int n,
max_dl = 1, /*zmienna będzie przechowywać maksymalną długość ciągu*/
poczatek, /*zmienna będzie przechowywać początek szukanego ciągu*/
dl = 1, p = 0; /*zmienne pomocnicze*/
int tab[1000000]; //deklaracja tablicy przechowująca wczytane liczby
/* lub dynamicznie: int *tab = new int[1000000];*/
cin>>n; //wczytanie zmiennej określającej ilość liczb w całym ciągu
cin>>tab[0];
poczatek = p = 0;
for(int i=1;i<n;i++) //wczytanie ciągu liczb i określenie początku
{
cin>>tab[i]; //najdłuższego ciągu rosnącego
if(tab[i]>tab[i-1]) //sprawdzenie czy następny jest większy od poprzedniego
{
++dl;
if(dl>max_dl) //sprawdzenie czy aktualna długość rosnącego ciągu
{
max_dl = dl; //jest większa od dotychczas najdłuższego
poczatek = p;
}
}
else
{
p = i; //resetowanie początku
dl = 1; //resetowanie aktualnej długości ciągu
}
}
/*wypisanie szukanego ciagu*/
for(int i = poczatek;i<poczatek + max_dl;i++)
cout<<tab[i]<<" ";
return 0;
}