Programowanie i algorytmy

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