嘉兴网站建设多少时间,wordpress 仿主题,建设银行管官方网站,夸克浏览器网页版给定一个包含整数的二维矩阵#xff0c;子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。
矩形的总和是该矩形中所有元素的总和。 在这个问题中#xff0c;具有最大和的子矩形被称为最大子矩形。
例如#xff0c;下列数组#xff1a; 0 -2 -7 0 9 2 -6 2 -4…给定一个包含整数的二维矩阵子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。
矩形的总和是该矩形中所有元素的总和。 在这个问题中具有最大和的子矩形被称为最大子矩形。
例如下列数组 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩形为 9 2 -4 1 -1 8 它拥有最大和15。
输入格式 输入中将包含一个N*N的整数数组。 第一行只输入一个整数N表示方形二维数组的大小。 从第二行开始输入由空格和换行符隔开的N2个整数它们即为二维数组中的N2个元素输入顺序从二维数组的第一行开始向下逐行输入同一行数据从左向右逐个输入。 数组中的数字会保持在[-127,127]的范围内。
输出格式 输出一个整数代表最大子矩形的总和。
数据范围 1≤N≤100 输入样例 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出样例 15
代码如下
#include iostream
using namespace std;
const int N 110;
int a[N][N];
int main()
{int n;cinn;for (int i 1;in;i)for (int j 1;jn;j){int x;cinx;a[i][j] a[i-1][j]x;}int res -1e8;for (int i 1;in;i){for (int j i;jn;j){int f 0;for (int k 1;kn;k){int cnt a[j][k]-a[i-1][k];f max(f,0)cnt;res max(res,f);}}}coutresendl;}
