Finding the rectangle with maximum perimeter weight in a 2D array
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&lt;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&lt;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&lt;j_2} (x_{j_1}+y_{j_2})$ in $O(n)$. In total, for each $i_1&lt;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.