2D Max Sum of Subarray – Kadane’s algorithm

Themistoklis Haris

Consider a matrix M m\times n with integer values. We seek to find a rectangular subarray of M whose sum of elements is maximized.

\begin{matrix} 5 & -4 & -3 & 4 \\ -3 & -4 & 4 & 5 \\ 5 & 1 & 5 & -4 \end{matrix}

First, let’s examine the 1D version of the problem. The brute force approach would be O(n^2) as we would have to examine all subarrays of M and build up the sums incrementally. A cleverer way is by using Dynamic Programming in Kadane’s algorithm.

Let P(i) denote the maximum sum subarray of M ending at index i. We can easily see how the following recursive formula holds:

P(i) = \left\{ \begin{array}{ll} M[i], &\text{if } i=0 \\ \max\{M[i], M[i]+P(i-1)\}, & \text{otherwise} \end{array} \right.

 

After finding P(i) for all i, we can loop through those values to get the maximum one. The time complexity is O(n).

For the 2D version of the problem, we employ a small trick. We examine the space between all possible pairs of columns. Let c_1 and c_2 \geq c_1 be two columns of M. Then we want to constructively construct an array T such that T[i] holds the sum of all values of row i of M between the two columns. On T we run Kadane’s algorithm for 1D to get our solution. This algorithm runs in O(n^3) over the O(n^4) brute force approach.