108 - Maximum Sum

You may solve this problem with a technique called summed area table, also known as integral image.

A small trick to make your codes simpler is to use sentinel: Index your matrix starting from \(1\) rather than from \(0\) and fill elements of integral image at \(0\)-row and \(0\)-column with \(0\)’s so that you will not get index out of bound error when computing rectangle sum.

Creative Commons License
This blog by Che-Liang Chiou is licensed under a Creative Commons Attribution 4.0 International License.