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)
?