# 2428. Maximum Sum of an Hourglass
###### tags: `Leetcode` `Medium`
Link: https://leetcode.com/problems/maximum-sum-of-an-hourglass/description/
## 思路
可以暴力解 时间复杂度为 $O(MN)$
也可以用prefix解 时间复杂度是一样的
## Code
brute force

class Solution {
    public int maxSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        for(int i=0; i+2<m; i++){
            for(int j=0; j+2<n; j++){
                ans = Math.max(ans, 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]);
            }
        }
        return ans;
    }
}

prefix

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