Maximum Sum of an Hourglass
You are given an m x n integer matrix grid.
We define an hourglass as a part of the matrix with the following form:
- Three adjacent cells in a row.
- One cell centered directly below them.
- Three adjacent cells in the row below that.
Return the maximum sum of the elements of an hourglass.
Note that an hourglass cannot be rotated and must be entirely contained within the matrix.
Example 1
6 2 1 3 4 2 1 5 9 2 8 7 4 1 2 9
Input
grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]Output
30The hourglass with the maximum sum is 6 + 2 + 1 + 2 + 9 + 2 + 8 = 30.
Example 2
1 2 3 4 5 6 7 8 9
Input
grid = [[1,2,3],[4,5,6],[7,8,9]]Output
35There is only one hourglass in the matrix, with the sum 1 + 2 + 3 + 5 + 7 + 8 + 9 = 35.
Constraints
- m == grid.length
- n == grid[i].length
- 3 <= m, n <= 150
- 0 <= grid[i][j] <= 10^6