top1编程
← 返回题目
题解

最大子矩阵

1 条题解

  • 0
    @ 2026-7-28 22:45:08
    #include<bits/stdc++.h>
    using namespace std;
    #define N 105
    #define INF 0x3f3f3f3f
    int n, a[N][N], b[N], s[N][N];//b[j]:子矩阵第j列的加和 s[i][j]:第j列的第1行到第i行的元素加和 
    int mx = -INF;
    int main()
    {
        cin >> n;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
            { 
                cin >> a[i][j];
                s[i][j] = s[i-1][j] + a[i][j];
            }
        for(int i1 = 1; i1 <= n; ++i1)//子矩阵第一行为原矩阵的第i1行,最后一行为原矩阵的第i2行 
            for(int i2 = i1; i2 <= n; ++i2)
            {
                for(int j = 1; j <= n; ++j)
                    b[j] = s[i2][j] - s[i1-1][j];
                int sum = 0;
                for(int j = 1; j <= n; ++j)//双指针法求最大子段和
                {
                    if(sum < 0)
                        sum = b[j];
                    else
                        sum += b[j];
                    mx = max(mx, sum);
                }
            }
        cout << mx;
        return 0;
    }
    
    • 1