PHP Coding Puzzle 4 : Find the Largest Sum of a Rectangular Submatrix

Welcome to the forth PHP coding puzzle !

You are given a matrix of integers, and you need to write a PHP function that will find the largest sum of any rectangular submatrix in the matrix. A submatrix is a rectangular subset of the matrix.

For example, given the matrix:

[  [1, 2, -1, -4, -20],
  [-8, -3, 4, 2, 1],
  [3, 8, 10, 1, 3],
  [-4, -1, 1, 7, -6]
]

The largest sum of any rectangular submatrix is 29, which is the sum of the submatrix:

[
  [-3, 4, 2],
  [8, 10, 1],
  [-1, 1, 7]
]

Here’s the function signature:

function maxSubMatrix($matrix) {
  // Your code here
}

You can assume that the input matrix is non-empty and rectangular (i.e., all rows have the same number of columns).

The solution is already available in the next page 😉 Feel free to share with us your solution here in comments or Github.