I have working code that finds the maximum sum of elements within a sub-rectangle of a 2D array. I'm wondering if there are any optimization techniques I could use to improve its performance.
The input is
The output
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
//TODO if max_sum already found in this windows size
int main()
{ int max_sum = INT_MIN;
int loopCount = 0; // for performance checking
//INPUT for 2D array field
int field[4][5] = {
{0, -5, 3, 4, 9},
{10, 21, 18, -11, 0},
{0, -2, 5, 9, 11},
{12, 7, 8, 3, -1}};
int fieldCol = 5; // INPUT for Y dimension of field
int fieldRow = 4; // INPUT for X simension of field
int window_size = 6; // INPUT for the maximum area of subrectangle
//output 0 and exit program for window_size 0
if (window_size <= 0)
{
printf("0");
exit(0);
}
// incase of window_size larger than area of field
int max_area = (fieldCol * fieldRow);
if (window_size > max_area)
{
window_size = max_area;
}
for (int X = 0; X < fieldRow; X++) // start position of x
{
for (int Y = 0; Y < fieldCol; Y++) // start position of y
{
for (int x = X; x < fieldRow; x++) // end position of x
{
for (int y = Y; y < fieldCol; y++) // end position of y
{
int sum = 0;
int count = 0;
//sum of all elements from starting(X,Y) to ending(x,y) position
for (int c_x = X; c_x <= x; c_x++)
{
for (int c_y = Y; c_y <= y; c_y++)
{
loopCount++; //benchmarking
sum += field[c_x][c_y];
count++; //count for subrectangle area
if(count>window_size){
break;
}
}
}
//set max_sum incase of the area of subrectangle is lower or equal to window_size
if (sum > max_sum && count <= window_size)
{
max_sum = sum;
}
}
}
}
}
printf("%d", max_sum);
printf("\nloop count %d", loopCount);
return 0;
}
The algorithm can be optimized by storing a 2-D array of cumulative sums. For efficiency, include an initial row containing all zeros, and an initial column containing all zeros, and fill in the remaining elements of the array as described below:
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+
| 0 | | | | | |
+---+---+---+---+---+---+
| 0 | | | | | |
+---+---+---+---+---+---+
| 0 | | | | A | B |
+---+---+---+---+---+---+
| 0 | | | | C | X |
+---+---+---+---+---+---+
In the above, the initial row and column have been set to all zeros, A, B, and C, contain the sum of the elements of the subrectangle from the top left corner up to and including the element. To fill in the element X, note that B contains the sum of all the elements above it, C contains the sum of all the elements to its left, and A contains the sum of all the elements that are both above it AND to its left. So the cumulative sum so far is B + C - A, and the value of X is the cumulative sum so far plus the input value to be added to the cumulative sum (B + C - A + input).
The given input array and its cumulative sum array are shown below:
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | -5| 3 | 4 | 9 | | 0 | 0 | -5| -2| 2 | 11|
+---+---+---+---+---+ +---+---+---+---+---+---+
| 10| 21| 18|-11| 0 | | 0 | 10| 26| 47| 40| 49|
+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | -2| 5 | 9 | 11| | 0 | 10| 24| 50| 52| 72|
+---+---+---+---+---+ +---+---+---+---+---+---+
| 12| 7 | 8 | 3 | -1| | 0 | 22| 43| 77| 82|101|
+---+---+---+---+---+ +---+---+---+---+---+---+
INPUT CUMULATIVE SUMS
The sum of the elements of any subrectangle can be found with a bit of arithmetic:
· · +------------+ +------+ · +------------+ +------+ ·
| | | | | | | |
| | | | | | | |
· +-----+ = | | - | | · - +------------+ + +------+ ·
| | | | | |
| | | | | |
· +-----+ +------------+ +------+ · · · · · · ·
In words, sum of elements of the subrectangle equals the sum of elements up to the bottom right corner of the subrectangle minus the sum of elements to the left of the subrectangle minus the sum of elements above the subrectangle plus the sum of elements that are both to the left and above the subrectangle.
For example:
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | | | | | | | 26| | 40| |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | 5 | 9 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | 8 | 3 | | | | | 43| | 82| |
+---+---+---+---+---+ +---+---+---+---+---+---+
INPUT CUMULATIVE SUMS
5 + 9 + 8 + 3 = 25 82 - 43 - 40 + 26 = 25
The following modified code calculates 2-D array of cumulative sums from the input, and uses it in the search for the maximum subrectangle sum for all subrectangles no larger than the window size.
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
//TODO if max_sum already found in this windows size
int main()
{ int max_sum = INT_MIN;
int loopCount = 0; // for performance checking
//INPUT for 2D array field
int field[4][5] = {
{0, -5, 3, 4, 9},
{10, 21, 18, -11, 0},
{0, -2, 5, 9, 11},
{12, 7, 8, 3, -1}};
int fieldCol = 5; // INPUT for Y dimension of field
int fieldRow = 4; // INPUT for X dimension of field
int window_size = 6; // INPUT for the maximum area of subrectangle
int sums[fieldRow + 1][fieldCol + 1];
//output 0 and exit program for window_size 0
if (window_size <= 0)
{
printf("0");
exit(0);
}
// Fill in cumulative sums array
for (int Y = 0; Y <= fieldCol; Y++)
{
loopCount++; //benchmarking
sums[0][Y] = 0;
}
for (int X = 1; X <= fieldRow; X++)
{
loopCount++; //benchmarking
sums[X][0] = 0;
for (int Y = 1; Y <= fieldCol; Y++)
{
loopCount++; //benchmarking
sums[X][Y] = sums[X - 1][Y] - sums[X - 1][Y - 1] +
sums[X][Y - 1] + field[X - 1][Y - 1];
}
}
for (int X = 0; X < fieldRow; X++) // start position of x - 1
{
for (int Y = 0; Y < fieldCol; Y++) // start position of y - 1
{
for (int x = X + 1; x <= fieldRow; x++) // end position of x
{
int height = x - X;
int area = 0;
if (height > window_size)
{
// area of width 1 subrectangle is too large
break;
}
for (int y = Y + 1; y <= fieldCol; y++) // end position of y
{
int sum;
loopCount++; //benchmarking
area += height;
if (area > window_size)
{
// area of subrectangle is too large
break;
}
//sum of all elements from starting(X+1,Y+1) to ending(x,y) position
sum = sums[x][y] - sums[X][y] + sums[X][Y] - sums[x][Y];
//set max_sum incase of the area of subrectangle is lower or equal to window_size
if (sum > max_sum)
{
max_sum = sum;
}
}
}
}
}
printf("%d\n", max_sum);
printf("loop count %d\n", loopCount);
return 0;
}
Output:
57
loop count 165
The above loop count includes the construction of the sums array from the field array. If the input element values are being read in from an external stream, there is no need to store them in the field array, because they can be read in on the fly as the sums array is being constructed.
This is the location of the subrectangle no larger than the window size of 6 with the maximum element sum:
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | | | | | | 0 | | -2| | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | 21| 18| | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | -2| 5 | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | 7 | 8 | | | | | 22| | 77| | |
+---+---+---+---+---+ +---+---+---+---+---+---+
INPUT CUMULATIVE SUMS
21 + 18 +
(-2) + 5 +
7 + 8 = 57 77 - 22 - (-2) + 0 = 57