Нахождение максимальной разницы ч / б индекса в массиве с ограничением a [i] <= a [j], где i <j

Question

Вот мой код, показывающий неправильный ответ на нескольких тестовых примерах. Кто-нибудь может сказать мне, где он терпит неудачу. Я не могу понять это даже после нескольких попыток.

#include <iostream>
using namespace std;

int main() {
    //code
    int t,n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        long long int a[n],max=0;
        for(int i=0;i<n;i++)
            cin >> a[i];
        int i=0,j=n-1;
        while(i<=j)
        {
            if(a[j]>=a[i]){
                max=j-i; break;}
            else if(a[j-1]>=a[i] || a[j]>=a[i+1])
               { max=j-i-1; break;}
            else
                i++;
                j--;
        }
        cout << max<<"\n";
    }
    return 0;
}

Answer 1

В O (n log n) есть решение:

1. Создать вектор индекса = 0 1 2 ... n-1

2. Сортировка (способом стабильный ) индексы i, j так, чтобы a[i] < a[i]

3. Определить значения max_index

   max_index[i]= max (index[j], j >= i)

Это можно вычислить рекурсивным образом O (n)

Для каждого индекса [i] определите index_max[i+1] - ind[i]); и определите максимальное из них

Максимум, который мы получили, и есть искомое значение.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int diff_max (const std::vector<long long int> &a) {
    int n = a.size();
    std::vector<int> index(n), index_max(n);
    int dmax = 0;
    std::iota (index.begin(), index.end(), 0);
    std::stable_sort (index.begin(), index.end(), [&a] (int i, int j) {return a[i] < a[j];});
    index_max[n-1] = index[n-1];
    for (int i = n-2; i >= 0; --i) {
        index_max[i] = std::max (index_max[i+1], index[i]);
    }
    for (int i = 0; i < n-1; ++i) {
        dmax = std::max (dmax, index_max[i+1] - index[i]);
    }
    return dmax;
}
    

int main() {
    int t, n;
    std::cin >> t;
    while(t--) {
        std::cin >> n;
        std::vector<long long int> a(n);
        for (int i = 0; i < n; ++i)
            std::cin >> a[i];
        
        auto max = diff_max (a);
        std::cout << max << "\n";
    }
    return 0;
}

Answer 2

Один известный случай, когда алгоритм не работает:

1 
5
5 7 6 2 3

Результат в этом случае равен 0, но он должен быть 2.

Если первые два условия не выполняются удовлетворен, тогда вы увеличиваете i, здесь вы только сравниваете i с j и j-1, но может быть другое значение k, такое, что k < j-1 и (i,j) являются ответом.