I can't wrap my head aroung Painting the barn gold

Problems and Contests
#1

http://www.usaco.org/index.php?page=viewproblem2&cpid=923
I’ve already solved the silver version pretty effortlessly, but I couldn’t figure out how the rectangle positioning works even after reading the official solution, specifically, I couldn’t understand how to find the maximum subarray sum in 2D, can you please help me?

#2

What don’t you understand about it?

#3

Thanks for replying
I don’t understand how maximum rectangle sum in a 2dimensional prefix matrix in a time different than O(n^4).
That’s my main struggle.

#4

You just don’t get the time complexity of the official implementation?

#5

I think so

#6

There’s a maximum of three nested loops. There’s no while loops or anything complicated like that, so the complexity should follow from there.