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
- field: 2D Array
- fieldRow: size of array in X dimension
- fieldCol: size of array in Y dimension
- window_size: The size of window
The output
- the maximum sum of elements within a sub-rectangle
<code>#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;
}
</code>
<code>#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;
}
</code>
#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;
}