最大子矩阵和
目录
/*
* @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;
}
历史评论
开始评论