A possible solution for the interview problem

Few days ago I have published a post in which presenting a problem received by me at an interview. Meanwhile I managed to find a solution and what I could achieve was a visual representation of the algorithm used to find the solution along with its pseudo-code description. I am still “struggling” to represent this algorithm in C language.

Before to proceed just a remainder of problem requirements:

1. a squared matrix is given as input, it can be read from keyboard using scanf or any other input stream read function
2. the matrix must have integer elements, positive and negative
3. the requirement is to find the “sub-rectangle” having the maximum sum of its elements

The approach is the following:

basically the program, or the function which is supposed to solve this problem, needs to check the sum of every possible sub-rectangle (it has to make an exhaustive search)
below I represented to way the algorithm iterates through each possible sub-rectangle, the integers that hold a certain position in the matrix are not taken into consideration, they will be substituted by matrix’s indexes. Here a 4×4 example is given but the algorithm has to be valid for a generic case

There are four counters, x1, x2, y1, y2 which are iterating through the elements. There will be a sum_max variable which will be the result returned by the function and a temporary variable to store intermediate values.

x1 and y1 will be the origin elements from where the search will be iteratively expanded. In the case presented above x1 and y1 are both 0 (suppose indexes are from 0 till N-1) and then y2 increases till the maximum value. After this set of iterations is done x2 increases by one.

Attention ! In case of second row of squares in the picture, when x2 is increased by one, also elements on the first row are taken into consideration and added to the calculated sum. So in case of second row in the picture it is not like this:

This will be considered at another iteration, we’ll see it later.

When the algorithm finishes all the iterations having the origin x1=0 and y1=0, y1 is incremented:

Basically all the iterations having as origin x1=0 and y1=1 are presented above.

The algorithm goes onwards until x1 reaches the maximum possible value, then y1 is incremented and the origin will be x1=1 and y1=0. All the iterations for this case are presented below:

The algorithm continues until sum of the last rectangle is calculated, the one composed only by the element x1=N y1=N.

If I’ll have to translate this in pseudo-code, this will look something like this:

initialize the SUM variable with the first element x1=0 y1=0
initialize the TEMP variable with the first element x1=0 y1=0

iterate from x1=0, until x1=N-1

iterate from y1=0, until y1=N-1

iterate from x2=0, until x2=N-1

iterate from y2=0, until y2=N-1

TEMP = TEMP + a[x1][y2]

check if TEMP is greater than SUM

if YES assign SUM=TEMP

for sure this is a very simplified version and an inaccurate one, but generally this is the way the iterations are done (first y2 iterator varies until reaches maximum value, then x2 is incremented and the number of elements at each previous step is doubled,, you can remark in the pictures that second row of tables duplicates the elements analyzed previously, the third step triples them and so on … after the algorithm finished iterating the y2 and x2 – length of subrectangles indicators – then the origin is moved and algorithm continues as before)

Total number of iterations (of existing sub-rectangles for a NxN matrix) is