Алгоритм для оценки монотонности массива (т.е. оценка “sortedness” массива)

Править: Ничего себе, много больших ответов. Да, я использую это в качестве функции фитнеса для оценки в некотором роде качества, выполненного генетическим алгоритмом. Таким образом, стоимость оценки важна (т.е. это должно быть быстро, предпочтительно O(n).)

Как часть приложения AI, с которым я играю, я хотел бы смочь оценить массив кандидата целых чисел на основе его монотонности, иначе его "sortedness". В данный момент я использую эвристику, которая вычисляет самое долгое отсортированное выполнение и затем делит это на длину массива:

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return longestRun;
}

Это - хорошее начало, но ему не удается принять во внимание возможность, что могут быть "глыбы" отсортированных подпоследовательностей. Например:

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

Этот массив делится в три отсортированных подпоследовательности. Мой алгоритм оценит его как отсортированных только 40%, но интуитивно, это должно получить более высокий счет, чем это. Существует ли стандартный алгоритм для этого вида вещи?