hdu 1081 & poj 1050 To the Matrix 最大子矩阵之和

缘起

【1】中讲解了一维的最大片段和, 本题将它推广到了二维. poj 1050 To the Matrix

hdu 1081和此题一模一样~

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你一个n^2矩阵（n<=100）,矩阵中的整数的绝对值<=127
求最大子矩阵和

【输入】
第一行是N, 然后是N^2个数.

【输出】
最大子矩阵的和

【样例输入】
4
0 -2 -7 0 
9 2 -6 2
-4 1 -4  1 
-1 8  0 -2

【样例输出】
15

【限制】
1s

本题也算是一道经典题了. 面试的时候也有考过.

如果纯暴力的话, 枚举矩阵的左上角和右下角, 然后计算子矩阵的和的话，则复杂度是O(N^4*N^2)=O(n^6). 对于n=100 可以到达10^12(1w亿), 这是不可接受的. 一定会被T掉. 至多接受O(N^3)的复杂度.

算法是

上图j、k固定，i变动(1~n), 则就是一个一维数组

上述子矩阵的和就是上图标出来的行的部分和的片段和

复杂度是O(N^2)的，比纯暴力快了4个数量级！！！算法的力量！！！

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 "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,a[105][105],s[105][105], m[105][105], ans = -0x3f3f3f3f, dp[105]; // m[j][k]是从第j列到第k列的部分和的最大片段和(对应一个子矩阵)

int foo(int j, int k) // j列到k列的部分和的最大片段和
{
	int t = s[1][k]-s[1][j-1], ret = t;
	for (int i = 2; i<=n; i++)
	{
		t = max(t,0)+ s[i][k]-s[i][j-1];
		ret = max(ret, t);
	}
	return ret;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1;i<=n;i++)
	{
		for (int j = 1; j<=n;j++)
		{
			scanf("%d", a[i]+j);
			s[i][j] = s[i][j-1]+a[i][j];
		}
	}
	for (int j = 1; j<=n; j++)
	{
		for (int k = j; k<=n; k++)
		{
			m[j][k] = foo(j,k); // m[j][k]就是固定j列到k列关于行i的最大部分和
		}
	}
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1; j<=n; j++)
		{
			ans = max(ans, m[i][j]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 232kB
Length 867
Lang C++
Submitted 2019-09-12 20:47:26
Shared
RemoteRunId 20856148

参考

【1】https://yfsyfs.github.io/2019/07/20/%E7%BB%8F%E5%85%B8dpdp-%E6%B1%82%E6%9C%80%E5%A4%A7%E7%89%87%E6%AE%B5%E5%92%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97/