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