UVA 108 Maximum Sum
题面翻译
给定一个含有正负数的二维数组，找出有最大和的子矩阵。矩阵的和指矩阵中所有元素的和。 一个子矩阵是任意在总矩阵中大小为1x1或更大的邻近子数组，例如在下面的矩阵中: 0 −2 −7 0
9 2 −6 2
−4 1 −4 1
−1 8 0 −2
(最大子矩阵)在左下方:
9 2
−4 1
−1 8
并且和为15.
输入:
包括一个N和NxN的矩阵 N<=100 矩阵中的数字在区间[-127,127]内
输出:
最大子矩阵的和
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2样例输出 #1
15solution
采用贪心算法，先计算从起点(0,0)位置到(i,j)位置为终点矩阵的和，并记为rec_sum[i][j]，然后可以求得从起点(x1,y1)位置到(x2,y2)位置为终点矩阵的和，即rec_sum[x2][y2]-rec_sum[x1-1][y2]-rec_sum[x2][y1-1]+ rec_sum[x1-1][y1-1]，然后可以遍历整个数字计算起点(x1,y1)位置到(x2,y2)位置为终点矩阵的和，并得到最大值
//
// Created by Gowi on 2023/11/29.
//
#include <iostream>
#define N 150
using namespace std;
int main() {
int n;
cin >> n;
int arr[N][N] = {0};
int rec_sum[N][N] = {0}; //sum[i][j]以(0,0)位置为起点，(i,j)位置为终点的矩阵内各元素的和
int row_sum[N][N] = {0}; //row_sum[i][j] 从(i,0)到(i,j)的和
int res = -999999999;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> arr[i][j];
row_sum[i][j] = row_sum[i][j - 1] + arr[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= i; ++k) {
rec_sum[i][j] += row_sum[k][j];
}
}
}
for (int x1 = 1; x1 <= n; ++x1) {
for (int y1 = 1; y1 <= n; ++y1) {
for (int x2 = x1; x2 <= n; ++x2) {
for (int y2 = y1; y2 <= n; ++y2) {
res = max(res,
rec_sum[x2][y2] - rec_sum[x1 - 1][y2] - rec_sum[x2][y1 - 1] +
rec_sum[x1 - 1][y1 - 1]);
}
}
}
}
cout << res << endl;
}