2
$\begingroup$

[Problem Description]: enter image description here

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!

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – Evil
    Oct 11, 2020 at 17:45
  • 3
    $\begingroup$ Great start: en.m.wikipedia.org/wiki/Summed-area_table $\endgroup$
    – Evil
    Oct 11, 2020 at 18:04
  • 1
    $\begingroup$ @D.W. It's one of the questions in my algorithm assignment. $\endgroup$
    – Frank
    Oct 12, 2020 at 2:56
  • 2
    $\begingroup$ @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 :) $\endgroup$
    – Frank
    Oct 12, 2020 at 3:02
  • 1
    $\begingroup$ Any relation to this question? $\endgroup$ Oct 19, 2020 at 17:27

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot! It really helps! $\endgroup$
    – Frank
    Oct 28, 2020 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.