Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int main() {
- int n = 23;
- //int* v = new int[n];
- int v[] = {8,3,1,5,39,20,21,100,123,22,55,62,72,54,1,3,2,6,3,5,29,10};
- /*
- *cout<<"vectorul ";
- *for (int i = 0; i < n; i++)
- * cin>>v[i];
- */
- //D[i][0] holds leftmost position of a number larger than all numbers through position i (left->right)
- //D[i][1] holds rightmost position of a number larger than all numbers through position i (right->left)
- int** D = new int*[n];
- for (int i = 0; i < n; i++)
- D[i] = new int[2];
- D[0][0] = 0;
- D[n - 1][1] = n - 1;
- for (int i = 1; i < n; i++)
- if (v[i] < v[D[i - 1][0]]) D[i][0] = D[i - 1][0];
- else D[i][0] = i;
- for (int i = n - 2; i >= 0; i--)
- if (v[i] < v[D[i + 1][1]]) D[i][1] = D[i + 1][1];
- else D[i][1] = i;
- //cat timp nu indeplineste conditia ma tot duc la dreapta. dupa ce am gasit una caut alta disjuncta, poate e mai buna. daca nu gaseste niciuna problema nu are solutie
- //e o subsecventa maxima (local) cu extremitatile cum trebuie daca capatul drept(D[i][1]) al celui de-al doilea nr din ea e
- // capatul stang al penultimului
- int max_dif = 0;
- int beg = -1; int k = 0;
- while (k < n) {
- while (k < n - 1 && D[D[k + 1][1] - 1][0] != k) k++;
- if (k < n - 1 && D[D[k + 1][1] - 1][0] == k && D[k + 1][1] - k > max_dif) { //hm............
- max_dif = D[k+1][1] - k;
- beg = k;
- }
- k++;
- }
- cout<<"subsecventa de lungime maxima: "<<endl;
- if (beg >= 0)
- for (int i = beg; i <= D[beg + 1][1]; i++)
- cout<<v[i]<<" ";
- else cout<<"nu exista";
- cout<<endl;
- //cin.sync(); cin.get();
- return 0;
- }
Add Comment
Please, Sign In to add comment