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

Question

[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

I am asked to give:

(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?

Thanks a lot in advance!

Answer 1

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<j_2$, 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<j_1} [A(i_1,j) + A(i_2,j)]\right] + \left[\sum_{i=i_1}^{i_2} A(i,j_2) + \sum_{j \leq j_2} [A(i_1,j) + A(i_2,j)]\right]. $$ 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<j_2} (x_{j_1}+y_{j_2})$ in $O(n)$. In total, for each $i_1<i_2$ 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)$.

This answers your first question. I'll let you check whether these methods can help with the second question.