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

Possible Solution :

Here’s one way to solve the problem:

function maxSubMatrix($matrix) {
  $nRows = count($matrix);
  $nCols = count($matrix[0]);

  // Initialize the maximum sum to negative infinity
  $maxSum = PHP_INT_MIN;

  // Loop through all possible left columns
  for ($left = 0; $left < $nCols; $left++) {
    // Initialize an array to keep track of the current sum of each row
    $currRowSums = array_fill(0, $nRows, 0);

    // Loop through all possible right columns
    for ($right = $left; $right < $nCols; $right++) {
      // Update the current row sums by adding the values in the current column
      for ($row = 0; $row < $nRows; $row++) {
        $currRowSums[$row] += $matrix[$row][$right];
      }

      // Find the maximum sum of any contiguous subarray in the current row sums
      $maxRowSum = maxSubArray($currRowSums);

      // Update the maximum sum if the maximum row sum is greater
      $maxSum = max($maxSum, $maxRowSum);
    }
  }

  return $maxSum;
}

function maxSubArray($nums) {
  $n = count($nums);
  $maxSum = $nums[0];
  $currSum = $nums[0];

  for ($i = 1; $i < $n; $i++) {
    $currSum = max($nums[$i], $currSum + $nums[$i]);
    $maxSum = max($maxSum, $currSum);
  }

  return $maxSum;
}

The function uses a dynamic programming approach to find the largest sum of any rectangular submatrix in the matrix. It loops through all possible pairs of left and right columns, and for each pair, it calculates the current row sums as the sum of the values in the columns from left to right for each row.

It then uses the maxSubArray function from the previous puzzle to find the maximum sum of any contiguous subarray in the current row sums. This is the largest sum of any rectangular submatrix that includes the current columns.

It updates the maximum sum seen so far if the largest sum of any rectangular submatrix that includes the current columns is greater than the current maximum sum. At the end of the loops, the function returns the maximum sum seen, which is the largest sum of any rectangular submatrix in the matrix.