Untitled

#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;

}