# Finding the rectangle with maximum perimeter weight in a 2D array

[Problem Description]:

Given an array of size $$N \times N$$, the task is to find the rectangle with maximum perimeter weight in the array. The perimeter is defined as the number of cells on the sides. The perimeter weight of a rectangle is defined as the sum of all the values lying on the sides of the rectangle.

For example, the above image shows an array of size 5*5. Each cell has a value. The pink cells form the perimeter of the rectangle with upper left cell (0,0) and lower right cell (2,3). The perimeter is 10. The perimeter weight is (1-1+0+4+2+1+0+2-5-1) = 3

(1): an $$O(N^3)$$ algorithm to find a rectangle with the maximum weight.

(2): an $$O(N^3)$$ algorithm to find a rectangle with the maximum weight with perimeter no greater than a given constant L.

I really have no idea about how to do. Could anyone give me some idea about these 2 problems?

• What have you tried? What if you iterate over all X, Y, Width, Height and sum? Can you optimise it? What could be stored as partial result?
– Evil
Oct 11, 2020 at 17:45
• Great start: en.m.wikipedia.org/wiki/Summed-area_table
– Evil
Oct 11, 2020 at 18:04
• @D.W. It's one of the questions in my algorithm assignment. Oct 12, 2020 at 2:56
• @Evil I've tried to create 2 matrix with the same dimension that store the prefix sum of the rows of the original matrix and the prefix sum of the columns. But I stucked. Thanks to you, I have more ideas about how to do :) Oct 12, 2020 at 3:02
• Any relation to this question? Oct 19, 2020 at 17:27

Let us denote the entries of the array by $$A(i,j)$$.
Fix the first and last rows of the rectangle $$i_1,i_2$$. For $$j_1, the perimeter of the corresponding rectangle is $$\sum_{i=i_1}^{i_2} [A(i,j_1) + A(i,j_2)] + \sum_{j=j_1}^{j_2} [A(i_1,j) + A(i_2,j)] = \\ \left[\sum_{i=i_1}^{i_2} A(i,j_1) - \sum_{j Let us denote the first term by $$x_{j_1}$$ and the second by $$y_{j_2}$$. Using appropriate precomputation, it is possible to compute the arrays $$x_j,y_j$$ in $$O(n)$$. We can also compute $$\max_{j_1 in $$O(n)$$. In total, for each $$i_1 we can compute the maximum perimeter in $$O(n)$$. Since there are $$O(n^2)$$ choices for $$i_1,i_2$$, the entire algorithm runs in $$O(n^3)$$.