题目
给出一个N [2<=N<=100],并给出一个N*N的矩阵,矩阵中的数为[-127,127]之间。求出矩阵中一块子矩阵的最大和。
输入样例
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
输出样例
15
解题思路
每读入一个数,就求出它那列的前缀和,最后直接利用前缀和进行计算子矩阵和(其实就是最大连续数列的和),时间复杂度是O(n^3)。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[101][101],n;
int main()
{
memset(a,0,sizeof(a));
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
int l;
scanf("%d",&l);
a[i][j]=a[i-1][j]+l;//求一列的前缀和
}
int maxn=-2147483647;
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)//以防出现j<i,若j<i,下面算式求不了
{
int t=0;
for (int k=1;k<=n;k++)
{
t+=a[j][k]-a[i-1][k];//求一个子矩阵的和
maxn=max(maxn,t);//求最大的子矩阵和
t=max(t,0);
}
}
printf("%d",maxn);
return 0;
}