Given an NxNxN binary array (containing only 0's or 1's), how can we obtain the largest cuboid with a non-trivial solution i.e. in O(N^3) ?
--
It is the same problem that Find largest rectangle containing only zeros in an N×N binary matrix but in an upper dimension. Also, in my case, the largest rectangle can "cross the edge" of the array i.e. the space is like a torus for a 2D matrix.
For a 2D array, if the entry is :
00111
00111
11000
00000
00111
the solution depicted by 'X' is
00XXX
00XXX
11000
00000
00XXX
I've done the computation for a NxN binary array and find a solution for the largest rectangle problem in O(N^2) by following the idea in http://tech-queries.blogspot.de/2011/03/maximum-area-rectangle-in-histogram.html. But I don't know how to apply it for a 3D array.
--
Example for a 3x3x3 array where the solution "cross the edge":
111
100
011
111
001
111
011
110
011
the solution should be:
1XX
100
0XX
1XX
001
1XX
0XX
110
0XX