Maximum Sum of an Hourglass

You can use a simple approach to find the maximum sum of an hourglass in a given grid by iterating through the elements and considering every possible hourglass shape.

Here’s a Python function to find the maximum sum of an hourglass:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        max_sum = float('-inf')
        m, n = len(grid), len(grid[0])

        # Iterate through the grid, and make sure to stop 2 rows and columns before the end
        # to prevent an out-of-bounds error when looking at the next hourglass.
        for i in range(m - 2):
            for j in range(n - 2):
                # Calculate the sum of the current hourglass
                hourglass_sum = grid[i][j] + grid[i][j + 1] + grid[i][j + 2] + \
                                grid[i + 1][j + 1] + \
                                grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2]

                # Compare to the maximum sum found so far
                max_sum = max(max_sum, hourglass_sum)

        return max_sum

The solution iterates through the grid, considering each element as the top-left corner of an hourglass. It then adds the values of the corresponding hourglass shape and checks if this sum is greater than the maximum sum found so far. If it is, the maximum sum is updated.

The code runs in O(m * n) time, where m and n are the dimensions of the grid, which is efficient for the given constraints.