The Problem

I'm interested in finding an efficient algorithm for the following problem:

Let's say we have an n-dimensional matrix A[i_1,...,i_n] of integers (positive or negative). I want to find a list of indices [(j_11,...j_1n),...,(j_k1,...,j_kn)] such that the following sum is maximized:

Sum of A[i_1,...i_n] where there exists some m <= k such that i_1 <= j_m1, i_2 <= j_m2, ... i_n <= j_mn

Note that k is not fixed in this problem, so the output array can be any size.

To clarify, in two dimensions (n=2), this would be the equivalent of selecting an arbitrary number of rectangles with one vertex at the origin and summing all entries in the union of these rectangles.

For example, in this two-dimensional example below, the optimal answer consists of two indices, [(0,2), (2,0)]. (The index (0,0) is the upper left corner).

 ----------------
|  1  |  2     3 |
|-----|----------
|  2  | -2    -3
|     |
|  3  | -1     1
 -----

Solution in the Two-Dimensional Case

I was able to find an algorithm for the two-dimensional case in O(N^2) time (where N is the length of each dimension). We can think of the problem as drawing a path from the lower left corner of my matrix to the upper right (if we envision our matrix as above) such that the "half" of the matrix to the upper left of the path is maximized. Then, the following dynamic programming approach is sufficient:

For simplicity's sake, I will reference the matrix layout from the example above. Transform the matrix as follows: for each cell, replace it by the sum of itself and all cells in a up-left diagonal line from it. For example, B[2,1] = A[2,1] + A[1,0]. In the example above, we have the following transformation:

 ----------------                ----------------
|  1  |  2     3 |              |  1  |  2     3 |
|-----|----------               |-----|----------
|  2  | -2    -3       ---->    |  2  | -1    -1  
|     |                         |     |
|  3  | -1     1                |  3  |  1     0
 -----                           -----

Now, note that the sum along any path from the lower left corner of B to the upper right corner of B is the same as the sum of all cells that are above and left (inclusively) of the same path in A. Thus, we have transformed this problem into a simple Find the maximum path in a matrix problem which can be solved using dynamic programming in O(N^2) time.

Question

Unfortunately, this approach does not scale well into 3-dimensions and beyond (as far as I can tell). The reason is because we can no longer apply the same transformation since we must use a surface to separate two halves of a cube instead of a 1-D path (as we did above). However, my intuition tells me there shouldn't be a fundamental difference between 2-dimensions and higher dimensions in this case. Is there a generalized O(N^n) algorithm for the n-dimensional version of this problem? Not sure if there is a simple generalization to my algorithm that can be applied to the higher dimensional cases, or if we need to use a completely different approach. Any guidance is appreciated!