In this lesson, given a 2-D array, we’ll find a matrix with the maximum sum.

Again, we’ll first write the simpler and more straightforward version of the code, and then we’ll optimize the code and make it more efficient!. Think of the submatrix as a window of varying sizes (dynamic-sized array) that we extend across the 2-D array to find the maximum sum rectangle.

If all the values were positive, we could say the entire array, when added, gives the maximum sum. However, we can have negative values too.

2-D array

Let’s now try and find the maximum rectangle in a 2-D array.

All possible windows

Say we have a 2-D array of 4x4 dimensions, then all of its possible windows would be as shown in the illustration below:

If we look at the illustration above, the first window anchored at point [0,0] first extends by column and then by row. The same is true for windows anchored at all the other points.

Once we understand what all the possible windows are, we can write code to display them.

Algorithm for exploring all the windows

Here’s the pseudocode for exploration:

  • For each starting pair (sri, sci) where sri is (0 to rows-1) and sci is (0 to cols-1)

    • For each ending pair (eri, eci) where eri ∈\in (sci to rows-1) and eci ∈\in (0 to cols-1)

      • Display the pairs [sri,sci] and [eri,eci]

Look at the code below:

Press + to interact
#include <iostream>
#include <unistd.h>
using namespace std;
#define MaxRows 100
#define MaxCols 100
#define Capacity 1000
void allPossibleWindows(int R[][MaxCols], int Rows, int Cols)
{
	// for each starting row index 
	for (int sri = 0; sri < Rows; sri++)
	{
		// for each starting column index
		for (int sci = 0; sci < Cols; sci++)
		{
			// for each ending row index
			cout << "Anchored at[" << sri << "," << sci << "]: " << endl << endl;
			for (int eri = sri; eri < Rows; eri++)
			{
				// for each ending column index
				for (int eci = sci; eci < Cols; eci++)
				{
					cout << "[" << sri << "," << sci << "]" <<
						"[" << eri << "," << eci << "]  ";
				}
			}
			cout << endl << endl;
		}
	}
}
int main()
{
	int R[MaxRows][MaxCols] = { { 10, 10, -40 },
								{-80, 40, 10  },
								{ 30, 80, 100 }
							   };
	int Rows = 3, Cols = 3;
	allPossibleWindows(R, Rows, Cols);
	return 0;
}

Subwindow with maximum sum (slowest version)

So far, we’ve seen that to test all the possible windows of a 2-D array, we’ll need at least four for loops.

Here are the pseudocode-level algorithmic details::

  • Call the matrix value anchored at [0,0] as the max.
  • For each starting position (sri,sci) and ending position (eri, eci) (this is basically four nested loops),
    • Compute the sum of the window [sri, sci] to [eri,eci] (another two nested loops).
    • Check if it is maximum.
      • Update max.

Look at the animation below to understand the working of our algorithm.

Implementation using six nested loops

Inside our four for loops, we initialize a variable called WinSum to calculate the window sum. We then write a fifth for loop that runs from the starting row index sri to the ending row index eri. Inside this loop, we write another for loop to update the WinSum that runs from the starting column index sci to the ending column index eci.

We then check if WinSum is greater than MaxSumWindow. If it is, we update msri, msci, meri, meci, and MaxSumWindow.

Press + to interact
#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;
#define MaxRows 100
#define MaxCols 100
#define Capacity 1000
int MaximumSumSubRectangleSlow6NestedLoops(int M[][MaxCols], int Rows, int Cols,
	int &msri, int &msci, int &meri, int &meci)
{
	int MaxSumWindow = M[0][0];
	msri = 0, msci = 0, meri = 0, meci = 0;
	for (int sri = 0; sri < Rows; sri++)
	{
		for (int sci = 0; sci < Cols; sci++)
		{
			for (int eri = sri; eri < Rows; eri++)
			{
				for (int eci = sci; eci < Cols; eci++)
				{
					int WinSum = 0;
					for (int r = sri; r <= eri; r++)
					{
						for (int c = sci; c <= eci; c++)
						{
							WinSum += M[r][c];
						}
					}
					if (WinSum > MaxSumWindow)
					{
						msri = sri, msci = sci, meri = eri, meci = eci;
						MaxSumWindow = WinSum;
					}
				}
			}
		}
	}
	return MaxSumWindow;
}
int main()
{
	int R[MaxRows][MaxCols] = {
		{ 10, 10, -40 },
		{-80, 40, 10 },
		{ 30, 80, 100 }
	};
	int Rows = 3, Cols = 3,
		msri, msci,
		meri, meci;
	cout << "Maximum sum rectangle with N^6 is: " <<
		MaximumSumSubRectangleSlow6NestedLoops(R, Rows, Cols, msri, msci, meri, meci) << endl;
	cout << "Anchored at: (" << msri << "," << msci << ")" << endl;
	cout << "    Ends at: (" << meri << "," << meci << ")" << endl;
	return 0;
}

Subwindow with maximum sum (slower version)

Let’s try and see if we can improve the code above in terms of efficiency.

Using five nested loops

What if, instead of calculating the sum of all the windows of the previous rows again and again, we store the sum of the windows of the previous row and add that to the current row’s sum for each new window?

Let’s make an array called PrevRows[] in which we store the sum of the windows of the previous row.

Let’s assume that, given a 3x3 window M[][], our starting point of the subwindow is [0,0], and the ending point is [2,1].

Press + to interact
1 2 3
6 8 1
9 4 5

Then, when calculating the sum of all the windows till the ending point [2,1] (where 4 is stored), we would need to calculate the sum of all the windows from the beginning till [2,1]. However, what if we had an array PrevRows[] that had the sum of the windows till the previous row already stored?

Idea:

  1. We add the elements of the current row till the ending point element (ending column index). We store this linear sum inside the variable, LinearSum.
  2. We then add the sum of the previous row’s window stored at PrevRows[eci] (ending column index).

This is exactly like the illustration above, which displays all the possible windows. Only here, we store the previous windows’ sum in an array to keep from calculating all the previous window sums again.

Look at the animation below:

For instance, for the second row, PrevRows[] would contain {7, 17, 21}. So, for the element at [2,1], we would add the values in the third row (9 + 4 = 13) and then add the window sum stored till [1,1], which is 17 in this case. So, 13 + 17 = 30 is our window sum from [0,0] to [2,1].

Look at the code below and run it step by step to understand it better:

Press + to interact
#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;
#define MaxRows 100
#define MaxCols 100
#define Capacity 1000
int MaximumSumSubRectangleSlow5NestedLoops(int M[ ][ MaxCols ], int Rows, int Cols, 
                                                     int &msri, int &msci, int &meri, int &meci)
{
    int MaxSumWindow = M[0][0];
    msri=0, msci=0, meri=0, meci=0;
    // sri ->starting row index
    for(int sri=0; sri<Rows; sri++)
    {    
        // starting column index
        for(int sci=0; sci<Cols; sci++)
        {
            int PrevRows[MaxCols]={}; // declaring an array to store the sum of
                                       //  windows till the previous row
      
            int WinSum=0; // variable to store the sum of the current window
            // eri -> ending row index
            for(int eri=sri; eri<Rows; eri++)
            {
                // eci -> ending column index
                for(int eci=sci; eci<Cols; eci++)
                {
                    int LinearSum=0; // variable to store the linear sum (of elements 
                                            //of the current row till the eci element)
                    for(int c=sci; c<=eci; c++) 
                        LinearSum += M[eri][c];
                    
                    WinSum = PrevRows[eci]+LinearSum; //adding the linear sum and the window sum till the previous row
                    PrevRows[eci] = WinSum; // updating the PrevRows[] array with the current window sum
                    if(WinSum>MaxSumWindow)
                    {
                        msri=sri, msci=sci, meri=eri, meci=eci;
                        MaxSumWindow = WinSum;
                    }
                }
            }
        }
    }
    return MaxSumWindow;
}
int main()
{   
  int R[MaxRows][MaxCols] =     { { 10,  10,  -40},
                                  { -80,  40,  10},
                                  { 30,   80,  100}
                                };
    
    int Rows=3, Cols=3,
        msri, msci,
        meri, meci;
   
    cout << "Maximum sum rectangle with N^5 is: "<<MaximumSumSubRectangleSlow5NestedLoops(R, Rows, Cols, msri, msci, meri, meci)<<endl;
    cout << "Anchored at: (" << msri << "," << msci << ")" << endl;
	cout << "    Ends at: (" << meri << "," << meci << ")" << endl;
    return 0;
}

Now that we’ve seen and understood the above code, can you modify it so that it only contains four nested loops?

Subwindow with maximum sum (slow version)

We’re going to try to optimize the above code further by using only four loops this time.

Using four nested loops

If we look closely, we didn’t really need the inner fifth for loop.

Instead of resetting the LinearSum to 0 for each new eci (ending column index) for the same row, we could easily maintain the LinearSum and use it to add the current eci element to the value inside the LinearSum for the same row elements.

So, let’s remove the fifth for loop and instead only reset the LinearSum to 0 when we move to a new row, i.e., after the third for loop.

Press + to interact
#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;
#define MaxRows 100
#define MaxCols 100
#define Capacity 1000
int MaximumSumSubRectangleSlow4NestedLoops(int M[][MaxCols], int Rows, int Cols,
	int &msri, int &msci, int &meri, int &meci)
{
	int MaxSumWindow = M[0][0];
	msri = 0, msci = 0, meri = 0, meci = 0;
	for (int sri = 0; sri < Rows; sri++)
	{
		for (int sci = 0; sci < Cols; sci++)
		{
			int PrevRs[MaxCols] = {};
			int WinSum = 0;
			for (int eri = sri; eri < Rows; eri++)
			{
				int LinearSum = 0;
				for (int eci = sci; eci < Cols; eci++)
				{
					LinearSum += M[eri][eci];
					WinSum = PrevRs[eci] + LinearSum;
					if (WinSum > MaxSumWindow)
					{
						msri = sri, msci = sci, meri = eri, meci = eci;
						MaxSumWindow = WinSum;
					}
					PrevRs[eci] = WinSum;
				}
			}
		}
	}
	return MaxSumWindow;
}
int main()
{
	int R[MaxRows][MaxCols] = {
		{ 10, 10, -40 },
		{-80, 40,  10 },
		{ 30, 80, 100 }
	};
	int Rows = 3, Cols = 3,
		msri, msci,
		meri, meci;
	cout << "Maximum Sum rectangle with N^4 is: " << MaximumSumSubRectangleSlow4NestedLoops(R, Rows, Cols, msri, msci, meri, meci) << endl;
	cout << "Anchored at: (" << msri << "," << msci << ")" << endl;
	cout << "    Ends at: (" << meri << "," << meci << ")" << endl;
	return 0;
}

Subwindow with maximum sum (fastest version)

How about we try and see if the code can still be optimized?

Using three nested loops

We used Kadane’s approach in the previous lesson when finding the maximum sum of a subarray in a 1-D array. We changed the anchor position if, during the extension of the window, the sum became negative, and we discarded all the range of anchors between the starting of the anchor and the end index where the sum becomes negative.

Similar to Kadane’s approach for a 1-D array, we’re going to optimize the code using only three loops by not exhausting all the windows.

What we will do instead of exhaustively iterating all the windows, we iterate in this manner:

  • We fix the two rows.
  • The first anchored row sri ∈\in {0,…,Rows-1}.
    • Maintain AllColsSumsOnSri[] for aggregated 1-D rectangles (the sum of each column).
  • The second anchored row eri ∈\in {sri,…,Rows-1}.
    • Being anchored now in two rows, it should move exactly how Kadane’s algorithm works in 1-D. This means that at any place, if the sum of the column is negative, we do not extend that rectangle. Rather, we move the anchored position by reinitializing the Sum to zero and exploring only those rectangles that are starting one index forward column-wise. If any Sum is greater than the MaxSumWindow during this exploration, we update MaxSumWindow (along with its start and end positions).

For example, consider the following example:

Press + to interact
Matrix:
 2   1  -1 -14 -22
-8  -3   4   2   1
 3   8  10   1   3
-4  -1   1   7  -8

Look at the animation below:

Look at the code here:

Press + to interact
#include <iostream>
#include <iomanip>
#include <unistd.h>
using namespace std;
#define MaxRows 100
#define MaxCols 100
#define Capacity 1000
int MaximumSumSubRectangleSlow3NestedLoopsKadane(int M[][MaxCols], int Rows, int Cols,
	int &msri, int &msci, int &meri, int &meci)
{
	int MaxSumWindow = M[0][0];
	msri = 0, msci = 0, meri = 0, meci = 0;
	for (int sri = 0; sri < Rows; sri++)
	{
		int AllColsSumsOnSri[MaxRows] = {};
		for (int eri = sri; eri < Rows; eri++)
		{
			int Sum = 0;
			for (int s = 0, e = 0; e < Cols; e++)
			{
				AllColsSumsOnSri[e] += M[eri][e];
				Sum += AllColsSumsOnSri[e];
				if (MaxSumWindow < Sum)
				{
					msri = sri, meri = eri, msci = s, meci = e, MaxSumWindow = Sum;
				}
				if (Sum < 0)	// As soon as the window Sum is -ve we must need to leave that window
				{
					Sum = 0;
					s = e + 1;	// Start of the new window
				}
			}
		}
	}
	return MaxSumWindow;
}
int main()
{
	int R[MaxRows][MaxCols] = {
		{ 10, 10, -40 },
		{-80, 40,  10 },
		{ 30, 80, 100 }
	};
	int Rows = 3, Cols = 3,
		msri, msci,
		meri, meci;
	cout << "Maximum Sum rectangle with N^3 is: " << MaximumSumSubRectangleSlow3NestedLoopsKadane(R, Rows, Cols, msri, msci, meri, meci) << endl;
	cout << "Anchored at: (" << msri << "," << msci << ")" << endl;
	cout << "    Ends at: (" << meri << "," << meci << ")" << endl;
	return 0;
}

In computer science, this answer-storing technique of the previous regions and using those answers to compute the new is a very celebrated technique, famously known as dynamic programming. The most essential part of dynamic programming is that it uses the fact that the answer computation has a lot of intersections, and the answers of the previous can be stored and reused wherever we need them.

This significantly improves the efficiency of the algorithm.