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

Ответ 1

Здесь только O (N ^ 4).

Предположим, что вы храните кубиок в bool cuboid [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 in cuboid[x][y][z] where x_min <= x <= x_max

      // so lets compute for each cell in array2d,
      // if are only 1 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)).

Ответ 2

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

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

"пересечь границу" свойство массива обрабатывается очевидным образом: повторяйте каждый индекс дважды и сохраняйте все суммарные суммы не более 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) уменьшается, все большие значения удаляются из хвоста очереди. Если он еще больше уменьшается (очередь пуста), стек используется для восстановления значения "sum" и помещает соответствующее значение "M" в очередь.

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

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