I have an integer matrix of size `4n x 4n`

. I need to select a part of the matrix of size `n^2`

from which adds up to the most.

For example if `n = 3`

. I have a matrix of size `12 x 12`

. In the below picture, you can clearly see that `n^2`

square (outlined in red) adds up to the most. For simplicities sake, I made all the numbers 5, expect for 9 of the boxes which are `9999`

so its clear that that is the `n^2`

squares that add up to the most.

My approach to solving this problem was to essentially create a `n^2`

square and brute force the entire `4n x 4n`

matrix. However, that runs in `O(n^4)`

time complexity. How can I do it in `O(n^2)`

?