Finding the minimum value of all subsets in a 2D array Imagine a N by M 2D array of random positive integers and two coordinates (i1,j1), (i2,j2), which represent the upper-left bound and bottom-right bound of a subarray, respectively.  Is there a efficient algorithm to calculate all the minimum values of each subarray?
[[4, 10, 9, 7],
 [9, 8,  1, 2],
 [1, 21, 3, 1]]

In this example of a 3 by 4 grid, if the two coordinates were (0,1) and (2,2), the minimum in this case would be 1, out of the values 10,9,8,1,21,3.
Other than the naive solution of finding all subsets and calculating the minimum in this subarray, which would be well beyond O(n^4), I have also considered using a method similar to prefix sum by creating a separate 2D array and storing the minimum from (0,0) to (i,j) at the value (i,j), but this issue here is you can't account for the overlap like you do in prefix sums.
Is there a way to account for overlap or another, more efficient algorithm?
Thank you!
In one dimension, looking for the maximum sum, this is solved by Kadane's algorithm. The referenced page does discuss some of the history and gives pointers to efficient solutions for the two-dimensional problem.
Bentley in his seventh &quot;Programming Pearls&quot; column (see e.g. here) discusses the one-dimensional problem in depth, devising ever more efficient algorithms for it's solution. Bentley's columns (and much more) are collected in his book &quot;Programming Pearls&quot; (Addison-Wesley, 2nd edition 1999).