Dynamic Programming: Find the rectangle in a grid that has the largest sum

Question

I came across the following Dynamic Programming problem.

You have a grid of integers (so including negative numbers). Find the rectangle that has the largest sum of numbers.

Any idea how to do it for a whole matrix?

I solved it for a single array, so I pretty much followed what longest increasing subsequnce does, but only for contiguous numbers.

def array_largest_block(sequence)
  len = sequence.size
  parents = [nil]*len
  my_largest = sequence
  largest = sequence.max

  for index in (1...len)
    if my_largest[index] < my_largest[index] + my_largest[index - 1]
      my_largest[index] = my_largest[index] + my_largest[index - 1]
      parents[index] = index - 1
      largest = [largest, my_largest[index]].max
    end
  end

  end_index_of_largest_block = my_largest.find_index(largest)
  i = end_index_of_largest_block
  res = []
  res << sequence[i]
  while !parents[i].nil?
    i = parents[i]
    res << sequence[i]
  end
  return {l_sum: largest, start: i, end: end_index_of_largest_block}
end

So My thinking is,

1. find the sum of each square in the matrix (just 1x1 squares)
2. save the max for a possible answer
3. Run the same thing starting from smallest possible rectangle and calculate all of them until you find the max. Which is the DB part.

Any ideas? Or if you guys don't knwo the exact solution, which DP type algorithm should i look at?

Answer 1

This can be done in O(N^3), where N is the size of the matrix.

You basically choose the left and right column of the rectangle and then scan through the rows in linear time(using precomputed sums).

int totalBestSum = -10000000;
for (int leftCol = 1; leftCol <= N; leftCol++)
   for (int rightCol = leftCol; rightCol <= N; rightCol++)
   {
      int curSum = 0, curBestSum = -10000000;
      for (int row = 1; row <= N; row++) {
         int rowSum = sumBetween(leftCol, rightCol, row);
         curSum += rowSum;
         if (curSum > curBestSum) curBestSum = curSum;
         if (curSum < 0) curSum = 0;                   
      }

      if (curBestSum > totalBestSum) totalBestSum = curBestSum;
   } 

sumBetween is a function returning the sum of the numbers on a particular row between two columns. It can be implemented in constant time, using precomputed sums.

int sumBetween(int leftCol, int rightCol, int row)
{
    return sum[row][rightCol] - sum[row][leftCol - 1];
}

To compute the sum array:

for (int row = 1; row <= N; row++)
   for (int col = 1; col <= N; col++)
      sum[row][col] = sum[row][col - 1] + matrix[row][col];

Answer 2

Seems like a duplicate, but still, look here: Getting the submatrix with maximum sum?

It is possible to do in O(N^3).

And why on earth do you use the 'NP-complete' tags?:D