Problem Statement
Given a 2D array of positive and negative integers, find the sub-rectangle with the largest sum.
General Idea
-
Create another 2D array
A
, whereA[i][j]
is the sum of the sub-rectangle ranging from(0, 0)
to(i, j)
- \(O(n^2)\) -
Calculate the sum of each sub-rectangle - \(O(n^4)\)
Complexity: \(O(n^2 + n^4) \rightarrow O(n^4)\)
Note: This is the naive solution. Time complexity can be reduced to \(O(n^3)\) using this algorithm, which is why I don’t delve into the details of my solution.
Code
C++ code below.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, temp, sum, result;
vector< vector<int> > A;
int main()
{
while(scanf("%d", &N) != EOF)
{
A.clear();
A.resize(N);
// set sum and result to min value
sum = -127*100*100; result = -127*100*100;
// Create new matrix A
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
scanf("%d", &temp);
A[i].push_back(temp);
// Get sum from its top and add it to current value
if(i > 0) A[i][j] += A[i-1][j];
// Get sum from left and add it to current values
if(j > 0) A[i][j] += A[i][j-1];
// If both left and top wereadded,
// remove top left value because it was included
// when we got sum from left once and again when we got it from top
if(i > 0 && j > 0) A[i][j] -= A[i-1][j-1];
}
// Calcute the sum of each possible box,
// where (i, j) are starting points and (k, l) are ending points
// EXAMPLE
// first loop will compute all possible boxes from (0, 0) to (N, N)
// Next loop from (0, 1) to (N, N) and so on....
// To compute, for example, from (2, 2) to (5, 6)
// Take entry of (5, 6) which represents the sum from (0, 0) to (5, 6)
// Then remove left and top portions i.e
// TOP PORTION - remove from (0, 0) to (1, 6)
// LEFT PORTION - remove from (0, 0) to (5, 1)
// If removed both top and left portions, add (1, 1) to compensate
// Check if this sum > result, if true, result = sum
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++)
for(int k = i; k < N; k++) for(int l = j; l < N; l++)
{
sum = A[k][l];
if(i > 0) sum -= A[i-1][l];
if(j > 0) sum -= A[k][j-1];
if(i > 0 && j > 0) sum += A[i-1][j-1];
result = max(sum, result);
}
printf("%d\n", result);
}
}