【模拟】沙漏的最大总和【力扣第 313 场周赛】

题目

6193. 沙漏的最大总和

---

给你一个大小为 m x n 的整数矩阵 grid 。

按以下形式将矩阵的一部分定义为一个 沙漏 ：

返回沙漏中元素的 最大 总和。

**注意：**沙漏无法旋转且必须整个包含在矩阵中。

示例 1：

输入：grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]
输出：30
解释：上图中的单元格表示元素总和最大的沙漏：6 + 2 + 1 + 2 + 9 + 2 + 8 = 30 。

示例 2：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：35
解释：上图中的单元格表示元素总和最大的沙漏：1 + 2 + 3 + 5 + 7 + 8 + 9 = 35 。

提示：

• m == grid.length
• n == grid[i].length
• 3 <= m, n <= 150
• 0 <= grid[i][j] <= 10^6

解题

方法一：模拟

思路

根据题目给出的沙漏的定义，枚举矩阵中的每个沙漏计出总和并维护一个最大总和(max)返回即可。

具体来说，枚举矩阵中的 $grid[1\sim m-1][1 \sim n-1]$ 的位置作为沙漏中心，然后把沙漏的每一个点加起来算出该沙漏点总和。

代码

class Solution {
    public int maxSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int max = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                int sum = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] +
                    grid[i][j] + grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1];
                max = Math.max(max, sum);
            }
        }
        return max;
    }
}