题解 | #最大子矩阵#
最大子矩阵
https://www.nowcoder.com/practice/a5a0b05f0505406ca837a3a76a5419b3
先计算一个列和矩阵total，用于快速计算i-j列和（i-j列和[k]=total[j][k]-total[i-1][k]）
形成一个i-j列和数组arr后运用动态规划计算最大子序列，
最后遍历i，j后取得最大子矩阵。
#include<iostream>
using namespace std;
const int maxn=101;
int matrix[maxn][maxn];
int total[maxn][maxn]; //辅助数组，记录列和
int arr[maxn]; //记录i-j行列和
int dp[maxn]; //进行动态规划的数组
int getmaxdp(int n){ //由arr数组计算其最大子序列
dp[0]=arr[0];
int maximum=dp[0];
for(int i=1;i<n;i++){
dp[i]=max(arr[i],dp[i-1]+arr[i]);
maximum=max(maximum,dp[i]);
}
return maximum;
}
void gettotal(int n){ //用于计算total数组
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==0){
total[i][j]=matrix[i][j];
}else{
total[i][j]=total[i-1][j]+matrix[i][j];
}
}
}
return;
}
int getmaxmatrix(int n){ //计算最大子矩阵
int maximum=matrix[0][0];
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
for(int k=0;k<n;k++){ //计算i-j行的列和
if(i==0){
arr[k]=total[j][k];
}else{
arr[k]=total[j][k]-total[i-1][k];
}
}
int current=getmaxdp(n);
maximum=max(maximum,current);
}
}
return maximum;
}
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>matrix[i][j];
}
}
gettotal(n);
cout<<getmaxmatrix(n)<<endl;
}
return 0;
}
