Hard Problemsgridoptimization
Maximum sum rectangle
Given a 2D matrix of integers that may be positive or negative, find the axis-aligned rectangular submatrix whose entries add up to the largest possible total.
Note. This is typically solved by collapsing pairs of rows into a running column sum and applying Kadane's algorithm to it, rather than by one recurrence over a table.
Do this lesson first: house robberThe full breakdown and animated table for this problem are still being written. In the meantime, run the four questions on it yourself — that is the whole exercise.