Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int n; /// numarul de elemente
- int l[1001]; /// lungimea subsirului pana in pozitia i
- int poz[1001]; /// pozitia elementului care urmeaza dupa elementul i
- int v[1001];/// array cu elementele
- int main()
- {
- cin >> n;
- for(int i = 1; i <= n; i++)
- cin >> v[i];
- int j;
- l[n] = 1, poz[n] = -1;/// dupa ultumul numar nu mai urmeaza nici un alt element
- /// lungimea subsirul pe care il pot forma cu ultimul element este 1
- for(int i = n-1; i >= 1; i--)
- /// pornesc de la penultimul element
- for(l[i] = 1, poz[i] = -1, j = i+1; j <= n; j++)
- /// verific toate elementele de dupa el
- if(v[i] <= v[j] && l[i] < l[j]+1)
- /// daca elementul i este mai mic decat elementul j
- /// si lungimea subsirului de care apartine i este mai mica decat lungimea subsirului j
- poz[i] = j, l[i] = l[j]+1;
- /// lungimea subsirului i creste cu lungimea subsirului lui j
- /// elementul care urmeaza dupa i are pozitia j
- int pmax = 1;
- for(int i = 1; i <= n; i++)
- if(l[pmax] < l[i])
- pmax = i;/// determin pozitia primului element din cel mai mare subsir cerscator
- for(int i = pmax; i != -1; i = poz[i])
- /// parcurg de la pozitia primului elem pana la ultimul care va avea -1 ce inseamna ca e sfarsit de sir
- cout << v[i] << ' ';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement