1895

O(n^4) solutions...

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<int>> rows(m + 2, vector<int>(n + 2)), cols(rows), d1(rows), d2(rows);
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j) {
                rows[i][j] += grid[i - 1][j - 1] + rows[i][j - 1];
                cols[i][j] += grid[i - 1][j - 1] + cols[i - 1][j];
                d1[i][j] += grid[i - 1][j - 1] + d1[i - 1][j - 1];
                d2[i][j] += grid[i - 1][j - 1] + d2[i - 1][j + 1];
            }
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                for (int k = min(m - i, n - j); k > res; --k) {
                    int sum = d1[i + k][j + k] - d1[i - 1][j - 1];
                    bool match = sum == d2[i + k][j] - d2[i - 1][j + k + 1];
                    for (int l = 0; l <= k && match; ++l) {
                        match &= sum == rows[i + l][j + k] - rows[i + l][j - 1];
                        match &= sum == cols[i + k][j + l] - cols[i - 1][j + l];
                    }
                    res = match ? k : res;
                }
        return res + 1;
    }
};

-----------

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int rows=grid.size(), cols=grid[0].size();
        int dp[rows+1][cols+1][4];
        memset(dp, 0, sizeof dp);
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = dp[i][j][3] = grid[i][j];
                if(j-1 >= 0)
                    dp[i][j][0] += (dp[i][j-1][0]);
                if(i-1>=0)
                    dp[i][j][1] += (dp[i-1][j][1]);
                if(i-1>=0 && j-1>=0)
                    dp[i][j][2] += (dp[i-1][j-1][2]);
                if(j+1 <= cols-1 && i-1 >= 0)
                    dp[i][j][3] += (dp[i-1][j+1][3]);
                //cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<" "<<dp[i][j][2]<<" "<<dp[i][j][3]<<endl;
            }
        int ans = 1;
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                for(int k=min(i,j); k>0; k--){
                    int sx = i-k, sy=j-k;
                    int dsum, adsum;
                    bool same = true;
                    if(!sx || !sy)
                        dsum = dp[i][j][2];
                    else
                        dsum = dp[i][j][2]-dp[sx-1][sy-1][2];

                    int dx = i, dy = sy, ndx = sx, ndy = j;
                    if(ndx==0 || ndy==cols-1)
                        adsum = dp[dx][dy][3];
                    else
                        adsum = dp[dx][dy][3]-dp[ndx-1][ndy+1][3];

                    if(dsum != adsum) continue;
                    int csum = 0;
                    for(int r=sx; r<=i && same; r++){
                        if(!sy)
                            csum = dp[r][j][0];
                        else
                            csum = dp[r][j][0]-dp[r][sy-1][0];
                        //cout<<csum<<" "<<i<<" "<<j<<" "<<k<<endl;
                        if(csum != dsum){
                            same = false;
                        }
                    }

                    for(int c=sy; c<=j && same; c++){
                        if(!sx)
                            csum = dp[i][c][1];
                        else
                            csum = dp[i][c][1]-dp[sx-1][c][1];
                        if(csum != dsum)
                            same = false;
                    }
                    if(same)
                        ans = max(ans, k+1);
                }
            }
        }
        return ans;
    }
};