蓝桥杯-最大子阵


问题

给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。
其中,A的子矩阵指在A中行和列均连续的一块。
输入格式
输入的第一行包含两个整数n, m,分别表示矩阵A的行数和列数。
接下来n行,每行m个整数,表示矩阵A。
输出格式
输出一行,包含一个整数,表示A中最大的子矩阵中的元素和。
样例输入

3 3
-1 -4 3
3 4 -1
-5 -2 8

样例输出
10
样例说明
取最后一列,和为10。
数据规模和约定
对于50%的数据,1<=n, m<=50;
对于100%的数据,1<=n, m<=500,A中每个元素的绝对值不超过5000。


思路

这题我是用动态规划求解,如下图,假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵,如下所示(ari表示a[r][i],假设数组下标从1开始):

1
2
3
4
5
6
7
8
9
10
| a11 …… a1i ……a1j ……a1n |
| a21 …… a2i ……a2j ……a2n |
| ......................|
| ...................... |
| ar1 …… ari ……arj ……arn |
| ......................|
| ...................... |
| ak1 …… aki ……akj ……akn |
| ......................|
| an1 …… ani ……anj ……ann |

那么我们将从第r行到第k行的每一行中相同列的加起来,可以得到一个一维数组如下:
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn),那么从中我们就可以把一个求子矩阵 的问题转换成一个求最大子段和 的问题,从中求出解。那么问题又来了,什么是最大子段和?怎么求最大子段和?
首先,我们看一个问题:

给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值
比如当(a1,a2,a3,a4,a4,a6)=(-1,11,-1,13,-5,-2)时,最大子段和就为23。

用动态算法求解:
b[j]=max{a[i]+a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j],1<=j<=n。
由b[j]的定义可易知,当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。故b[j]的动态规划递归式为:
b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n。

最大子段和算法

1
2
3
4
5
6
7
8
9
10
11
12
int getMaxArray(int a[],int n){//求最大子段和
int max=a[0],temp=0;
for (int i=0;i<n;i++) {
if (temp>0) {
temp+=a[i];
}else {
temp=a[i];
}
max=max>temp?max:temp;
}
return max;
}


实现代码

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
#include "stdio.h"
#include<string.h>
int dp[100];
int getMaxArray(int a[],int n){//求最大子段和
int max=a[0],temp=0;
for (int i=0;i<n;i++) {
if (temp>0) {
temp+=a[i];
}else {
temp=a[i];
}
max=max>temp?max:temp;
}
return max;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int a[n][m];
for(int i=0;i<n;i++){
for (int j=0;j<m;j++) {
scanf("%d",&a[i][j]);
}
}
int res=a[0][0],tmp;
for (int i=0;i<n;i++) {
memset(dp, 0, sizeof(dp));//将dp数组置为0
for (int j = i; j < n; ++j) {
for (int k = 0; k < m; ++k) {
dp[k] += a[j][k];
}
tmp = getMaxArray(dp, n);
res = res > tmp ? res : tmp;
}
}
printf("%d\n", res);
}
-------------本文结束感谢您的阅读-------------

本文标题:蓝桥杯-最大子阵

文章作者:shenzekun

发布时间:2017年03月05日 - 16:03

最后更新:2017年11月13日 - 07:11

原始链接:http://www.shenzekun.cn/蓝桥杯-最大子阵.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

您的支持将鼓励我继续创作!