gistfile1.cpp

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