1895. 最大的幻方

思路

把所有可能性嘗試一遍，途中用前綴和去加速。

程式碼

前綴和

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 前綴和
        vector<vector<int>> rowSum(m + 1, vector<int>(n + 1, 0)); // 計算列和 (左上到右下)
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                rowSum[i + 1][j + 1] = rowSum[i + 1][j] + grid[i][j];
            }
        }
        vector<vector<int>> colSum(m + 1, vector<int>(n + 1, 0)); // 計算行和 
        for(int j = 0; j < n; ++j){
            for(int i = 0; i < m; ++i) {
                colSum[i + 1][j + 1] = colSum[i][j + 1] + grid[i][j];
            }
        }

        auto check = [&](int x, int y, int k) -> bool {
            int sum = rowSum[x + 1][y + k] - rowSum[x + 1][y];
            for(int i = x + 1; i < x + k; ++i) { // 檢查橫向和
                int current = rowSum[i + 1][y + k] - rowSum[i + 1][y];
                if(current != sum) return false;
            }
            for(int j = y; j < y + k; ++j) { // 檢查縱向和
                int current = colSum[x + k][j + 1] - colSum[x][j + 1];
                if(current != sum) return false;
            }

            int current = 0;
            for (int i = 0; i < k; ++i) { // 檢查主對角線
                current += grid[x + i][y + i];
            }
            if(current != sum)
                return false;
            
            current = 0;
            for(int i = 0; i < k; ++i) { // 檢查副對角線
                current += grid[x + i][y + k - 1 - i];
            }
            if(current != sum)
                return false;

            return true;
        };

        for(int k = min(m, n); k >= 2; --k) { // 最大的方形面積是邊長取小
            for(int x = 0; x <= m - k; ++x) {
                for(int y = 0; y <= n - k; ++y) { // 從大往小去試
                    if(check(x, y, k)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }
};

複雜度分析

• 時間複雜度：$O(n^3)$
• 空間複雜度：$O(n)$