CODEWITHSUNDEEP
algorithmoptimization
Reinstate Monica
Reinstate Monica

Reputation: 2480

finding rectangle in number grid with largest corner sum

Given a rectangular grid with width width and height height, a rectangle is defined by four natural numbers, left, right, top, and bottom, satisfying:

The corners of a rectangle are the positions of the grid at coordinates (left, top), (right, top), (left, bottom), and (right, bottom).

Given a rectangular grid of integers, the value of a rectangle is the sum of the numbers in the grid at the corners of the rectangle. Is there an efficient algorithm that, given such a grid, finds a rectangle with the maximum value? If necessary, we may constrain the range of numbers in the grid.

A brute force algorithm is quadratic in the size of the grid, width * height, because there are linearly many choices for each pair (left, top) and (right, bottom). But I am wondering if this problem can be solved in linear, linearithmic, or similar time.

Upvotes: 1

Views: 411

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

Suppose that the grid is m×n with m≤n. Here's a O(m2 n)-time algorithm. For each pair of rows (m choose 2), compute their element-wise sum and consider the sum of the two greatest entries of the resulting vector.

Upvotes: 2

Related Questions