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!