题目传送
题目描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×1)子矩阵。
比如，如下4×4的矩阵
0 -2 -7 09 2 -6 2 -4 1 -4 1-1 8 0 -2
的最大子矩阵是
9 2-4 1-1 8
这个子矩阵的大小是15。
输入
输入是一个N×N的矩阵。输入的第一行给出N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
输出
输出最大子矩阵的大小。
样例
输入数据 1
40 -2 -7 09 2 -6 2
-4 1 -4 1
-1 8 0 -2输出数据 1
15来源
一本通在线评测
解题思路，无代码
核心思路
将二维矩阵的最大子矩阵问题转化为一维数组的最大子数组问题（Kadane算法）。
关键步骤
- 1.
预处理列和
- •
用
t数组记录从第i行到第j行的列累加和
- •
- 2.
Kadane算法
- •
cm记录当前子数组最大和 - •
gm记录全局最大和 - •
递推公式：
cm = max(t[k], cm + t[k]) - •
更新公式：
gm = max(gm, cm)
- •
- 3.
矩阵遍历
- •
外层循环：上边界
i（0 ≤ i < n） - •
内层循环：下边界
j（i ≤ j < n） - •
每次更新
t数组后调用 Kadane 算法
- •
复杂度分析
- •
时间：O(n³)（双重行循环×单列遍历）
- •
空间：O(n)（存储列和）
边界处理
- •
矩阵全负时取最大单元素
- •
1×1矩阵直接返回
注：实际实现时需要处理输入输出格式，但思路本身不依赖具体语言实现。
#include<bits/stdc++.h>
using namespace std;
int kd(vector<int>&t)
{int cm=t[0],gm=t[0];for (int i=1; i<t.size(); i++){cm=max(t[i],cm+t[i]);gm=max(gm,cm);}return gm;
}int solve(vector<vector<int> >&mat)
{int n=mat.size();int gm=INT_MIN;for(int i=0; i<n; i++){vector<int>t(n,0);for(int j=i; j<n; j++){for(int k=0; k<n; k++){t[k]+=mat[j][k];}gm=max(gm,kd(t));}}return gm;
}
int main()
{int n;cin>>n;vector<vector<int> >mat(n,vector<int>(n));for(int i=0; i<n; i++){for(int j=0; j<n; j++){cin>>mat[i][j];}}cout<<solve(mat);return 0;
}此代码仅供参考，请勿纯抄
