Maximum Diamond Sum
MediumMatrix ยท HRT
Given a non-empty integer matrix grid, return the largest sum of any filled diamond that lies entirely inside it.
A diamond has a centre cell and a radius k >= 0, and covers every cell whose Manhattan distance from the centre is at most k. Radius 0 covers only the centre. Any radius is allowed as long as every covered cell is inside the grid. Cells may be negative.
Example 1
- Input:
- grid = [[1, -2, 3, 0, 1], [4, 2, 5, -1, 2], [-3, 6, 1, 2, -4], [2, 0, 4, -2, 3], [0, -1, 2, 1, -5]]
- Output:
- 18
- Explanation
- The diamond centred at row 2, column 2 with
k = 1sums to 18; growing it tok = 2adds cells that bring the sum down to 15.
Example 2
- Input:
- grid = [[-4, -2], [-7, -3]]
- Output:
- -2
Example 3
- Input:
- grid = [[5, -1, 2, 3]]
- Output:
- 5
Constraints
1 <= grid.length, grid[0].length <= 100- All rows have the same length
-10^9 <= grid[i][j] <= 10^9