题解 | 最大和子矩阵

#include <vector>
class SubMatrix {
  public:
    int sumOfSubMatrix(vector<vector<int> > mat, int n) {
        // write code here
        int res = mat[0][0];

        for (int top = 0; top < n; ++top) {
            vector<int>col_sum(n, 0);
            //compress
            for (int bottom = top; bottom < n; ++bottom) {
                for (int col = 0; col < n; ++col) {
                    col_sum[col] += mat[bottom][col];
                }
                int cur=col_sum[0], max_sub=col_sum[0];
                for(int i=1;i<n;++i)
                {
                    cur = max(col_sum[i], cur+col_sum[i]);
                    res = max(res, cur);

                }
            }

        }
        return res;

    }
};