title: Maximizing sum of union of rectangles in a matrix
body: <h1>The Problem</h1>
  <p>I'm interested in finding an efficient algorithm for the following problem:</p>
  <p>Let's say we have an n-dimensional matrix <code>A[i_1,...,i_n]</code> of integers (positive or negative). I want to find a list of indices <code>[(j_11,...j_1n),...,(j_k1,...,j_kn)]</code> such that the following sum is maximized:</p>
  <pre><code>Sum of A[i_1,...i_n] where there exists some m &lt;= k such that i_1 &lt;= j_m1, i_2 &lt;= j_m2, ... i_n &lt;= j_mn
  </code></pre>
  <p>Note that <code>k</code> is not fixed in this problem, so the output array can be any size.</p>
  <p>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.</p>
  <p>For example, in this two-dimensional example below, the optimal answer consists of two indices, <code>[(0,2), (2,0)]</code>. (The index <code>(0,0)</code> is the upper left corner).</p>
  <pre><code> ----------------
  |  1  |  2     3 |
  |-----|----------
  |  2  | -2    -3
  |     |
  |  3  | -1     1
   -----
  </code></pre>
  <h1>Solution in the Two-Dimensional Case</h1>
  <p>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 &quot;half&quot; of the matrix to the upper left of the path is maximized. Then, the following dynamic programming approach is sufficient:</p>
  <p>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, <code>B[2,1] = A[2,1] + A[1,0]</code>. In the example above, we have the following transformation:</p>
  <pre><code> ----------------                ----------------
  |  1  |  2     3 |              |  1  |  2     3 |
  |-----|----------               |-----|----------
  |  2  | -2    -3       ----&gt;    |  2  | -1    -1  
  |     |                         |     |
  |  3  | -1     1                |  3  |  1     0
   -----                           -----
  </code></pre>
  <p>Now, note that the sum along any path from the lower left corner of <code>B</code> to the upper right corner of <code>B</code> is the same as the sum of all cells that are above and left (inclusively) of the same path in <code>A</code>. Thus, we have transformed this problem into a simple <code>Find the maximum path in a matrix</code> problem which can be solved using dynamic programming in O(N^2) time.</p>
  <h1>Question</h1>
  <p>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!</p>