最大子矩阵和
目录
/*
* @Author : YaleXin
* @Email : me@yalexin.top
* @LastEditors : YaleXin
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int num[101][101], sums[101][101], temp[101];
int n;
int oneMatMaxSum(){
int nowSum = 0, maxSum = -128 * 100 - 1;
for(int i = 0; i < n;i++){
if (nowSum > 0)nowSum += temp[i];
else nowSum = temp[i];
maxSum = max(maxSum, nowSum);
}
return maxSum;
}
// 给出一个方阵 求最大子矩阵和
int main() {
ios::sync_with_stdio(false);
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &num[i][j]);
sums[i][j] = num[i][j];
}
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++)
sums[i][j] += sums[i - 1][j];
int maxSum = -128, nowSum;
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
// temp 保存的是从 第 i 行到 第 j 行所对应的矩阵每一列的和
for (int k = 0; k < n;k++){
if (i == 0)temp[k] = sums[j][k];
else temp[k] = sums[j][k] - sums[i - 1][k];
}
nowSum = oneMatMaxSum();
maxSum = max(nowSum, maxSum);
}
}
cout << maxSum << endl;
return 0;
}
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!
历史评论
开始评论