Алгоритм для подсчета количества допустимых блоков в перестановке [дубликат]

В этом вопросе есть небольшой «математический трюк», но он довольно прост, как только вы его получите. Однако остальная часть моего решения не будет соответствовать критериям O (n log n).

Математическая часть :

Для любых двух последовательных чисел их сумма равна 2k + 1 , где k - наименьший элемент. Для трех это 3k + 3 , 4: 4k + 6 и для N таких чисел это Nk + sum (1, N-1 ) . Следовательно, вам нужны два шага, которые можно выполнить одновременно:

1. Создайте сумму всех подмассивов.
2. Определите наименьший элемент подмассива.

Часть динамического программирования

Создайте две таблицы, используя результаты записей предыдущей строки, чтобы построить записи каждой последующей строки. К сожалению, я совершенно ошибаюсь, так как это все равно потребует проверок подмассивов n ^ 2. Фу!

Просто некоторые мысли:

На первый взгляд, это кажется невозможным: полностью отсортированный массив будет иметь O(n²) допустимых подблоков.

Таким образом, вам нужно будет считать более одного допустимого подблока за раз. Проверка достоверности субблока - это O(n). Проверка того, полностью ли отсортирован подблок, также O(n). Полностью отсортированный подблок содержит n-(n - 1)/2 допустимых подблоков, которые можно посчитать без дальнейшего разбиения этого подблока.

Теперь, очевидно, весь массив всегда является допустимым. Для подхода "разделяй и властвуй" необходимо разбить его на части. Есть две возможные точки разрыва: местоположение самого высокого элемента и самого низкого элемента. Если разбить массив на две части в одной из этих точек, включая экстремум в ту часть, которая содержит второй по высоте элемент, то не может быть допустимого подблока, пересекающего эту точку разрыва.

Если всегда выбирать экстремум, который дает более равномерное разбиение, это должно работать достаточно хорошо (в среднем O(n log n)) для "случайных" массивов. Однако я вижу проблемы, когда на вход подается что-то вроде (1 5 2 6 3 7 4 8), что, похоже, приводит к O(n²) поведению. (1 4 7 2 5 8 3 6 9) будет похожим (надеюсь, вы видите закономерность). В настоящее время я не вижу приёма, позволяющего отловить такой худший случай, но, похоже, для этого нужны другие методы разбиения.

(Это попытка сделать N.log(N) наихудший случай. К сожалению, она ошибочна - она иногда занижает подсчеты. Он неверно предполагает, что вы можете найти все блоки, просматривая только соседние пары меньших допустимых блоков. На самом деле вы должны просмотреть тройки, четверки и т.д., чтобы получить все большие блоки.)

Вы делаете это с помощью структуры, которая представляет субблок и очередь для субблоков.

  struct
c_subblock
{
  int           index   ;  /* index into original array, head of subblock */
  int           width   ;  /* width of subblock > 0 */
  int           lo_value;
  c_subblock *  p_above ;  /* null or subblock above with same index */
};

Выделите массив подблоков того же размера, что и исходный массив, и инициализируйте каждый подблок, чтобы в нем был ровно один элемент. Добавляйте их в очередь по мере выполнения. Если вы начнете с массива [ 7 3 4 1 2 6 5 8 ], то в итоге получите очередь следующего вида:

очередь: ( [7,7] [3,3] [4,4] [1,1] [2,2] [6,6] [5,5] [8,8] )

Значения { index, width, lo_value, p_above } для подблока [7,7] будут { 0, 1, 7, null }.

Теперь все просто. Простите за псевдокод на языке Си.

loop {
  c_subblock * const p_left      = Pop subblock from queue.
  int          const right_index = p_left.index + p_left.width;
  if ( right_index < length original array ) {
    // Find adjacent subblock on the right.
    // To do this you'll need the original array of length-1 subblocks.
    c_subblock const * p_right = array_basic_subblocks[ right_index ];
    do {
      Check the left/right subblocks to see if the two merged are also a subblock.
        If they are add a new merged subblock to the end of the queue.
      p_right = p_right.p_above;
    }
    while ( p_right );
  }
}

Я думаю, это найдет их все. Обычно это O(N log(N)), но для полностью сортированного или антисортированного списка это будет O(N^2). Я думаю, что на это есть ответ - когда вы строите исходный массив подблоков, вы ищете отсортированные и антисортированные последовательности и добавляете их в качестве подблоков базового уровня. Если вы ведете подсчет, увеличьте его на (width * (width + 1))/2 для базового уровня. Это даст вам счет, ВКЛЮЧАЯ все субблоки длиной 1.

После этого просто используйте цикл, описанный выше, проталкивая и выталкивая очередь. Если вы считаете, то вам нужно иметь множитель для левого и правого субблоков и умножить их вместе, чтобы вычислить приращение. Множитель - это ширина самого левого (для p_left) или самого правого (для p_right) субблока базового уровня.

Надеюсь, все понятно и не слишком глючно. Я просто набрасываю, так что это может быть даже неправильно. [Позднее примечание. Это не работает. См. примечание ниже]

Исходный массив не содержит дубликатов, поэтому сам должен быть последовательным блоком. Назовем этот блок (1 ~ n). Мы можем проверить, является ли блок (2 ~ n) последовательным, проверив, является ли первый элемент 1 или n, который равен O (1). Точно так же мы можем протестировать блок (1 ~ n-1), проверив, равен ли последний элемент 1 или n.

Я не могу превратить это в решение, которое работает, но, возможно, оно кому-то поможет ...