Ошибка алгоритма. Определите, был ли массив уже разбит на разделы (т.е. Один шаг быстрой сортировки)

Последний вопрос о финале моих алгоритмов сводил меня с ума в течение последнего месяца. Вот вопрос:

У вас есть массив A[0...n], напишите алгоритм (в "правильном" псевдокоде), который работает в O (n), который может определить, был ли этот массив уже разбит по отношению к некоторому индексу k, и если да, найдите k; if not then return -1;

Чтобы уточнить, Partition:

Для каждого элемента e в A[0...n], если e < A[k] поместите e в "левый" A[k], добавьте e в "правую" сторону A[k].

Итак, пример многораздельного массива (w.r.t. k = 11):

A = [4 2 5 3 7 4 2 6 8 4 1 10 10 10 20 11 15 13 28 99 11]

затем

myAlgo(A) -> (11)

или

A = [10, 20, 30, 40, 11, 100 , 150, 101, 125]

затем

myAlgo(A) -> (5)

но не:

A = [10, 20, 30, 40, 5]

myAlgo(A) -> (-1)

Моя первая мысль (которая была невероятно наивной) была настолько ужасной, что я буквально не могу выразить это словами. В основном, он непреднамеренно проверял, отсортирован ли массив и вытащил довольно случайное значение из середины.

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

Вот где я пытался (очень, очень плохо) реализовать это (с тестовым примером):

int myAlgo(const int* A, int n);

int main() {

    const int A[] = {10, 20, 30, 40, 11, 100, 150, 101, 125};

    int index;
    if((index = myAlgo(A, 9)) != -1) {
        printf("A[%d] = %d", index, A[index]);
    }
    else {
        printf("Not Partitioned >:/");
    }

    return 0;
}

int myAlgo(const int* A, int n) {
    // the index of the smallest possible number in the remainder of the list
    int minIdx = 0;

    // the index of the largest number we've encountered
    int maxIdx = 0;

    // index of possible partition "center"
    int kIdx = 0;

    bool isPart = false;

    for(int i=0; i < n; ++i) {
        if( A[maxIdx] <= A[i] )  {
            maxIdx = i;
            if(isPart == false)  { kIdx = i; minIdx = i;} // if we flipped then this is a good time to grab a partitioner index
            isPart = true;
        }
        else { isPart = false; minIdx = i; }
        printf("A[%d] = %d <==> A[%d]: %d : %c\n", maxIdx, A[maxIdx], i, A[i], (isPart?'T':'F'));
        if( A[minIdx] > A[i] ) { isPart = false; }
        printf("A[%d] = %d <==> A[%d]: %d : %c\n", minIdx, A[minIdx], i, A[i], (isPart?'T':'F'));
    }

    printf("A[%d] = %d : %c\n\n", kIdx, A[kIdx], (isPart?'T':'F'));

    // We gotta check this to make sure it is a valid list...
    if(isPart) return kIdx;
    else return -1;
}

Но, что неудивительно, мой результат: <Предварительно > <Код > A [0] = 10 < == > A [0]: 10: T A [0] = 10 < == > A [0]: 10: T A [1] = 20 < == > A [1]: 20: T A [0] = 10 < == > A [1]: 20: T A [2] = 30 < == > A [2]: 30: T A [0] = 10 < == > A [2]: 30: T A [3] = 40 < == > A [3]: 40: T A [0] = 10 < == > A [3]: 40: T A [3] = 40 < == > A [4]: ​​11: F A [4] = 11 < == > A [4]: ​​11: F A [5] = 100 < == > A [5]: 100: T A [5] = 100 < == > A [5]: 100: T A [6] = 150 < == > A [6]: 150: T A [5] = 100 < == > A [6]: 150: T A [6] = 150 < == > A [7]: 101: F A [7] = 101 < == > A [7]: 101: F A [6] = 150 < == > A [8]: 125: F A [8] = 125 < == > A [8]: 125: F A [5] = 100: F < - индекс прав... но isPart неверен

Не разбит на разделы > :/

Мне бы очень хотелось спать сегодня вечером, поэтому любые советы/подсказки/идеи/и т.д. были бы очень, очень оценены.

---

Woo! @Amit помог мне решить мою проблему, вот моя обновленная функция:

int partIdx2(const int* A, int n) {

    int* max = malloc(n * sizeof(int));
    int* min = malloc(n * sizeof(int));

    for(int i=0; i < n; i++)
    {
        if(i==0) {
            max[i] = A[i];
            min[n - 1] = A[n-1];
        }
        else {
            max[i] = MAX(max[i-1], A[i]);
            min[n - 1 - i] = MIN(min[n - 1 - i + 1], A[n - 1 - i]);
        }
    }

    for(int i=1; i < n-1; i++) {
        if(A[i] >= max[i-1] && A[i] <= min[i+1]) { 
            free(max);
            free(min);
            return i; 
        }
    }

    free(max);
    free(min);

    return -1;
}