You'll have to test every possible subrectangle, however you can start at the top-left and keep going left, so you can subtract the most left column of the subrectangle and add the new column each step. When you're done with the row, start with the next one.
NP-complete commented: be 100% sure, atleast before advising. +0