宁波方正建设监理网站,哈尔滨企业做网站,海口网站制作,九江哪里做网站题目描述 给定一个n*m的矩阵A#xff0c;求A中的一个非空子矩阵#xff0c;使这个子矩阵中的元素和最大。 其中#xff0c;A的子矩阵指在A中行和列均连续的一块。 输入 输入的第一行包含两个整数n, m#xff0c;分别表示矩阵A的行数和列数。 接下来n行#xff0c;每行m个整…题目描述 给定一个n*m的矩阵A求A中的一个非空子矩阵使这个子矩阵中的元素和最大。 其中A的子矩阵指在A中行和列均连续的一块。 输入 输入的第一行包含两个整数n, m分别表示矩阵A的行数和列数。 接下来n行每行m个整数表示矩阵A。 1n, m500A中每个元素的绝对值不超过5000。 输出 输出一行包含一个整数表示A中最大的子矩阵中的元素和。 样例输入 3 3 -1 -4 3 3 4 -1 -5 -2 8 样例输出 10
代码如下
#include iostream
using namespace std;
const int N 510;
int a[N][N];
int n, m;int main() {cin n m;for (int i 1; i n; i)for (int j 1; j m; j) {int x;cin x;a[i][j] a[i - 1][j] x;}int res -1e8;for (int i 1; i n; i)for (int j i; j n; j) {int sum 0;for (int k 1; k m; k) {sum max(0, sum) a[j][k] - a[i - 1][k];res max(sum, res);}}cout res endl;return 0;
}
