preface
本文是对最大子矩阵和的记录。这题就是对最大子段和的扩展。
从最大子段和的一维变成了二维数组的多维。我们要做的就是将二维转为1维,转化为更简单的最大子段和求解。
这里转化的思想就是对列值就行累加
比如
累计变成了4 6 -8就从两行变为了一行,利用最大子段和就能求解。
问题如下
有一个正整数和负整数组成的NxN矩阵，请编写代码找出元素总和最大的子矩阵。请尝试使用一个高效算法。
给定一个int矩阵mat和矩阵的阶数n，请返回元素总和最大的子矩阵的元素之和。保证元素绝对值小于等于100000，且矩阵阶数小于等于200。
测试样例：
1
2
3
4
5
6
7
8
9
10
| 3
1 2 -3
3 4 -5
-5 -6 -7
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
|
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <iostream>
#include <string>
#include <cstring>
#define MAX 1000
using namespace std;
int sum(int a[], int n) {
int result = 0, b = 0;
for (int i = 0; i < n; i++) {
if (b > 0) {
b += a[i];
} else {
b = a[i];
}
if (b > result) {
result = b;
}
}
return result;
}
int main() {
int n;
while(cin >> n) {
int a[MAX][MAX];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
int arr[MAX];
int final = 0;
for (int i = 0; i < n; i++) {
memset(arr, 0, sizeof(arr));
for (int j = i; j < n; j++) {
for (int k = 0; k < n; k++) {
arr[k] += a[j][k];
}
final = max(sum(arr, n), final);
}
}
cout<<final<<endl;
}
return 0;
}
|
参考
动态规划：最大子矩阵
To the Max
最大子段和
最大子矩阵和的问题
[编程题]最大和子矩阵