Najdłuższy spójny ciąg rosnący

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.

 

Dane wejściowe

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].

Dane wyjściowe

Szukany ciąg liczb.

Przykład

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

 

powrót