Sail


手在键盘敲很轻


最大子矩阵和

preface

本文是对最大子矩阵和的记录。这题就是对最大子段和的扩展。

从最大子段和的一维变成了二维数组的多维。我们要做的就是将二维转为1维,转化为更简单的最大子段和求解。

这里转化的思想就是对列值就行累加

比如

1
2
1 2 -3 
3 4 -5

累计变成了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
1
2
10
15

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++) { // 以第0,1,2...行为起始行开始叠加
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
最大子段和
最大子矩阵和的问题
[编程题]最大和子矩阵

© 2016-2019. | 由Hexo强力驱动 | 主题Huno | 渝ICP备17002561号 | 不装弱了,我要做大佬