Блог

Проверьте, существует ли индекс 0 <= k < n - 2 , такой, что элементы массива A[] , перемещаемые по часовой стрелке по k индексам, образуют обратный битонический массив. Мой подход к выполнению этого за O (n) время сложности:

 bool is_antibitonicable(int A[], int n) {
    // returns if there is such index k that 
    // after moving clockwise k elements of array
    // A[], that array is reverse bitonic
    // - strictly decreasing then strictly
    // increasing
    if (n < 3)
        return false;
    // if is_increasing[i] == 1 means this part of A[] is increasing,
    // == 0 means that part of A[] is decreasing, == -1 default
    int is_increasing[3] = { -1, -1, -1 };
    for (int i = 0, j; i < n - 1;) {
        if (A[i] < A[i   1]) { // if A[] is increasing
            j = 0;
            while (j < 3 amp;amp; is_increasing[j] != -1)
                j  ;
            if (j == 3)
                return false;
            is_increasing[j] = 1;
            while (i < n - 1 amp;amp; A[i] < A[i   1])
                i  ;
        }
        else if (A[i] > A[i   1]) { // check if decreasing
            j = 0;
            while (j < 3 amp;amp; is_increasing[j] != -1)
                j  ;
            if (j == 3)
                return false;
            is_increasing[j] = 0;
            while (i < n - 1 amp;amp; A[i] > A[i   1])
                i  ;
        }
        else // sequence of A[] is neither increasing nor decreasing
            return false;
    }
    // if A[] is only increasing/decreasing
    if (is_increasing[1] == is_increasing[2])
        return false;
    // if A[] is increasing->decreasing->increasing check if increasing
    // parts can be merged into one increasing sequence
    if (is_increasing[0] == 1 amp;amp; is_increasing[1] == 0 amp;amp; is_increasing[2] == 1)
        return (A[0] > A[n - 1]);
    // decreasing->increasing->decreasing
    if (is_increasing[0] == 0 amp;amp; is_increasing[1] == 1 amp;amp; is_increasing[2] == 0)
        return (A[0] < A[n - 1]);
    return true; // increasing -> decreasing or opposite
}
 

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

Ваше решение выглядит неплохо, но оно работает неправильно return false // if A[] is only increasing/decreasing . Такую последовательность всегда можно превратить сначала в уменьшающуюся, а затем в увеличивающуюся, повернув на единицу в правильном (соответствующем) направлении.