A solution that iterates over all possible squares (by selecting all combinations of an upper-left cell and side length) and computes sums of diagonals for each of them has complexity ~\mathcal O(N^4)~, which exceeds the time limit.

A faster solution, with complexity ~\mathcal O(N^3)~, works by selecting a central cell of a square and gradually expands the square outwards until reaching an edge, while keeping track of the current diagonal sums. Whenever expanding the current square, the diagonal sums are updated and the maximum beauty is updated as well, if the new beauty value is larger. In the end, we simply output the final maximum value.

The algorithm described above must cover two cases: when the square centre is a matrix cell (i.e. with an odd-length square side) and when it is a corner of four cells (with an even-length side). The latter case is marginally more involved to implement.