Найти самый большой кубоид, содержащий только 1 в двоичном массиве NxNxN

Question

Учитывая двоичный массив NxNxN (содержащий только 0 или 1), как мы можем получить самый большой кубоид с нетривиальным решением, т.е. в O (N ^ 3)?

-

Это та же проблема, что и Найти самый большой прямоугольник, содержащий только нули в двоичной матрице N × N , но в верхнем измерении.Также, в моем случае, самый большой прямоугольник может «пересекать край» массива, т. Е. Пространство является тором для 2D-матрицы.

Для 2D-массива, если запись:

00111
00111
11000
00000
00111

решение, обозначенное 'X':

00XXX
00XXX
11000
00000
00XXX

Я выполнил вычисление для двоичного массива NxN и нашел решение для самой большой проблемы прямоугольника в O (N ^ 2) с помощьюследуя идее в http://tech -queries.blogspot.de / 2011/03 / Maximum-Area-rectangle-in-Histogram.html .Но я не знаю, как применить его для трехмерного массива.

-

Пример для массива 3x3x3, где решение "пересекает край":

111
100
011

111
001
111

011
110
011

решение должно быть:

1XX
100
0XX

1XX
001
1XX

0XX
110
0XX

Answer 1

Это решение имеет сложность O (N ³ log ² N) (может быть оптимизировано до O (N ³ log N)).Потребуется дополнительный массив целых чисел размером 2 * 8 * N ³ .

1. Вычислить r (i, j, k): для каждого из N ² строк, вычислить совокупную сумму всех ненулевых элементов, сбросив ее при обнаружении нулевого элемента.
2. Выполните следующие шаги для различных значений K, используя Поиск золотого сечения (или поиск Фибоначчи), чтобы найти максимальный результат.
3. Вычислить c (i, j, k): для каждого из столбцов N ² вычислить накопленную сумму всех элементов с помощью r (i, j, k)> = K, сбрасывая его, когда найден элемент с r (i, j, k) этот ответ .
4. Выполните последний шаг для различных значений M, используя поиск по Золотому сечению, чтобы найти максимальный результат.
5. Вычислить сумму: для каждого из N ² значений 3-й координаты рассчитать накопленную сумму всех элементов с помощью c (i, j, k)> = M, сбросив ее, когда элемент с c (i,j, k) K M и при необходимости обновите лучший на данный момент результат.

Свойство «пересечь границу» массива обрабатывается очевидным образом: дважды повторяйте каждый индекс и сохраняйтевсе кумулятивные суммы не больше N.

Для многомерного случая этот алгоритм имеет O (N ^D log ^D-1 N) временную сложность и O (D *)N ^D ) Пространственная сложность.

---

Оптимизация до O (N ³ log N)

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

Для этого необходимо улучшить шаг 5.Он должен поддерживать двустороннюю очередь (заголовок которой содержит локальное значение M) и стек (сохраняя начальные позиции для всех значений M, исключенных из очереди).

Пока c (i, j,k) увеличивается, добавляется к хвосту очереди.

Если c (i, j, k) уменьшается, все большие значения удаляются из хвоста очереди.Если он еще больше уменьшается (очередь пуста), стек используется для восстановления значения «сумма» и помещения в очередь соответствующего значения «М».

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

Для многомерного случая эта оптимизация дает сложность O (N ^D log ^D-2 N).

Answer 2

Вот только O (N ^ 4).

Допустим, вы храните кубиод в кубическом кубоиде [N] [N] [N];

bool array2d[N][N];

for(int x_min = 0; x_min < N; x_min++) {
   //initializing array2d
   for(int y = 0; y < N; y++) {
      for(int z = 0; z < N; z++) {
         array2d[y][z] = true;
      }
   }

   //computation
   for(int x_max = x_min; x_max < N; x_max++) {
      // now we want to find largest cube that
      // X coordinates are equal to x_min and x_max

      // cells at y,z can be used in cube if and only if
      // there are only 1's in cuboid[x][y][z] where x_min <= x <= x_max

      // so lets compute for each cell in array2d,
      // if are only 1's in cuboid[x][y][z] where x_min <= x <= x_max
      for(int y = 0; y < N; y++) {
         for(int z = 0; z < N; z++) {
            array2d[y][z] &= cubiod[x_max][y][z];
         }
      }

      //you already know how to find largest rectangle in 2d in O(N^2)
      local_volume = (x_max - x_min + 1) * find_largest_area(array2d);

      largest_volume = max(largest_volumne, local_volume);
   }
}

Вы можете использовать тот же трюк, чтобы вычислить лучшее решение в X измерениях.Просто уменьшите проблему до размеров X-1.Сложность: O (N ^ (2 * X-2)).