Given a matrix with integer elements the problem is to find the maximum sum submatrix. The problem is stated and solved here using Kadane's algorithm for a 2D matrix.
Now I want to solve this problem for higher dimensions i.e. given a matrix in d-dimensional space design an algorithm that solves the same problem.
I wonder if you can do it in O(n^(2d-1)) time.
Any idea is appreciated.
You can compute the sum of a d-dimensional submatrix with 2^d lookups, 2^d/2 subtractions and (2^d/2)-1 additions by using a multi-dimensional Summed-area table.
The summed-area table is a matrix with the same dimensionality and size as the input matrix, where each element in the summed-area table is the sum of all all elements in the input matrix with indexes equal to or lower than that element in all dimensions. It can be calculated with a single pass over the matrix.
You could then find the maximum sum submatrix in O(n^2d) by iterating over each dimension in both start index and submatrix size, and computing the submatrix sum for those start indexes and sizes using the summed-area table. Basically you look up all the "corners" of your submatrix in the SAT and add or subtract the value to get the submatrix sum. When d is odd then for each corner, if the corner has an odd number of dimensions where it is the end index of the submatrix range then you add it, and if it has an even number then you subtract it. Vice versa when d is even. Example in 2D below (from the SAT Wikipedia page)
The submatrix with the highest total is the maximum sum submatrix.
Using Kadane's algorithm could reduce the inner two loops (start index and submatrix size of one of the dimensions) into one, making it O(n^(2d-1))
