# Untitled

By: a guest on May 17th, 2012  |  syntax: None  |  size: 1.81 KB  |  hits: 10  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <iostream>
2. using namespace std;
3.
4. int main() {
5.
6.     int n = 23;
7.     //int* v = new int[n];
8.     int v[] = {8,3,1,5,39,20,21,100,123,22,55,62,72,54,1,3,2,6,3,5,29,10};
9.     /*
10.      *cout<<"vectorul ";
11.      *for (int i = 0; i < n; i++)
12.      *    cin>>v[i];
13.      */
14.
15.     //D[i][0] holds leftmost position of a number larger than all numbers through position i (left->right)
16.     //D[i][1] holds rightmost position of a number larger than all numbers through position i (right->left)
17.     int** D = new int*[n];
18.     for (int i = 0; i < n; i++)
19.         D[i] = new int[2];
20.
21.     D[0][0] = 0;
22.     D[n - 1][1] = n - 1;
23.
24.     for (int i = 1; i < n; i++)
25.         if (v[i] < v[D[i - 1][0]]) D[i][0] = D[i - 1][0];
26.         else D[i][0] = i;
27.
28.     for (int i = n - 2; i >= 0; i--)
29.         if (v[i] < v[D[i + 1][1]]) D[i][1] = D[i + 1][1];
30.         else D[i][1] = i;
31.
32.     //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
33.     //e o subsecventa maxima (local) cu extremitatile cum trebuie daca capatul drept(D[i][1]) al celui de-al doilea nr din ea e
34.     // capatul stang al penultimului
35.     int max_dif = 0;
36.     int beg = -1; int k = 0;
37.     while (k < n) {
38.           while (k < n - 1 && D[D[k + 1][1] - 1][0] != k) k++;
39.           if (k < n - 1 && D[D[k + 1][1] - 1][0] == k && D[k + 1][1] - k > max_dif) {  //hm............
40.                             max_dif = D[k+1][1] - k;
41.                             beg = k;
42.                             }
43.           k++;
44.           }
45.
46.     cout<<"subsecventa de lungime maxima: "<<endl;
47.     if (beg >= 0)
48.     for (int i = beg; i <= D[beg + 1][1]; i++)
49.         cout<<v[i]<<" ";
50.     else cout<<"nu exista";
51.
52.     cout<<endl;
53.     //cin.sync(); cin.get();
54.     return 0;
55. }