Advertisement
Nita_Cristian

Subsir comun de lungime maxima

Feb 4th, 2020
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n; /// numarul de elemente
  6. int l[1001]; /// lungimea subsirului pana in pozitia i
  7. int poz[1001]; /// pozitia elementului care urmeaza dupa elementul i
  8. int v[1001];/// array cu elementele
  9.  
  10. int main()
  11. {
  12.     cin >> n;
  13.     for(int i = 1; i <= n; i++)
  14.         cin >> v[i];
  15.     int j;
  16.     l[n] = 1, poz[n] = -1;/// dupa ultumul numar nu mai urmeaza nici un alt element
  17.     /// lungimea subsirul pe care il pot forma cu ultimul element este 1
  18.     for(int i = n-1; i >= 1; i--)
  19.         /// pornesc de la penultimul element
  20.         for(l[i] = 1, poz[i] = -1, j = i+1; j <= n; j++)
  21.         /// verific toate elementele de dupa el
  22.             if(v[i] <= v[j] && l[i] < l[j]+1)
  23.             /// daca elementul i este mai mic decat elementul j
  24.             /// si lungimea subsirului de care apartine i este mai mica decat lungimea subsirului j
  25.                 poz[i] = j, l[i] = l[j]+1;
  26.                 /// lungimea subsirului i creste cu lungimea subsirului lui j
  27.                 /// elementul care urmeaza dupa i are pozitia j
  28.  
  29.     int pmax = 1;
  30.     for(int i = 1; i <= n; i++)
  31.         if(l[pmax] < l[i])
  32.             pmax = i;/// determin pozitia  primului element din cel mai mare subsir cerscator
  33.  
  34.     for(int i = pmax; i != -1; i = poz[i])
  35.         /// parcurg de la pozitia primului elem pana la ultimul care va avea -1 ce inseamna ca e sfarsit de sir
  36.         cout << v[i] << ' ';
  37.  
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement