2D Prefix Sums: Full Implementation at Staff Level

Concepts: py2DPrefixAdvanced, pyMaxSubmatrix, pyKadanePrefixComposition

Staff-level interviewers use 2D prefix sum problems to test spatial thinking and optimization mindset simultaneously. They know you can build a 1D prefix array. The question is whether you can reason about two dimensions cleanly, derive the inclusion-exclusion formula from first principles (not memory), handle edge cases at the matrix boundary, and articulate when 2D prefix sums are the right tool and when they are not. This section gives you all four of those capabilities. Complete Implementation with All Edge Cases The max_submatrix_sum bonus is what staff-level problems look like. Fix two rows r1 and r2. The column sum for each column c between r1 and r2 is a single number (computed in O(1) using the prefix array). Now you have a 1D array of column sums. Apply Kadane's algorithm to find