I have a three dimensional bit array A of dimension N x N x N. The question is to find a maximum volume cuboid in A, i.e. indices i1, i2, i3, j1, j2, j3, such that A(k1, k2, k3) = 1 for all i <= k <= j and volume = prod(j-i+1) is maximum.
The crucial claim is that I need complexity O(N^3) (up to logarithmical Term if necessary). Stating an algorithm for O(N^4) is easy. But the O(N^3) complexity seems to be a far harder problem. There are also many other discussions on exactly that problem online, unfortunately without a (correct) solution.
Thanks a lot for your appreciated help!
Best, Christian