前缀和思想

注意事项:
    

if(ans < 0) ans = 0; 
//当ans<0时，如果继续包括前边子矩阵，结果肯定是减小的，所以直接舍弃前边子矩阵

参考代码:

#include
using namespace std;
const int N = 510; 
int n,m;
int sum = INT_MIN;     // 答案最初设置一个极小值
int mp[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int t;cin >> t;
            mp[i][j] = mp[i-1][j] + t;        //按列求和
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = i; j <= n; j ++){            // i，j限制子矩阵的行
            int ans = 0;
            for(int k = 1; k <= m; k ++){        // k 限制子矩阵的列
                ans += mp[j][k] - mp[i-1][k];
                if(ans > sum) sum = ans;
                if(ans < 0) ans = 0;     
            }
        }
    }
    cout << sum;
    return 0;
}