题目描述
二维前缀和暴力美学
注意事项:定义x1,y1 与 x2,y2直接的矩阵为遍历所求矩阵,但是x1,y1 一定要在 x2,y2左上或者相等
样例
/*
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
测试样例
*/
算法1
(暴力枚举) $O(n^4)$
二维前缀和暴力美学
时间复杂度 n^4
C++ 代码
#include<iostream>
#include<algorithm>
int const maxn=110;
int map[maxn][maxn];//原矩阵
int sum[maxn][maxn];//二维前缀矩阵和
using namespace std;
int main()
{
//输入数据
int n; cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>map[i][j];
//cout<<endl;
//二维前缀和处理
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
sum[i][j]=sum[i][j-1]+sum[i-1][j]+map[i][j]-sum[i-1][j-1];
//cout<<sum[i][j]<<" "; //这行可以看sum矩阵
}
//cout<<endl;//这一行加入sum矩阵格式输出
}
//cout<<endl;
//int count=0;
//用坐标遍历所有子矩阵并求出他的最大和
int max1=-1000,max2;
for(int x1=1;x1<=n;x1++)
for(int y1=1;y1<=n;y1++)
for(int x2=1;x2<=n;x2++)
for(int y2=1;y2<=n;y2++)
{
if(x1>x2||y1>y2) continue;//跳过注意事项1,也可以把第3,4个for 改成x2=x1 y2=y1
// count++;
max2=sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2];
// cout<<max2<<" ";
max1=max(max1,max2);
}
//cout<<endl;
cout<<max1<<" ";
//<<count<<endl;
/*
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
测试样例
*/
}