#1369. 子矩阵的和
子矩阵的和
题目背景
前面接触了子串的概念,本题我们需要用到子矩阵的概念。类比着理解,子矩阵就是在原来的矩阵当中挖出一个部分,保证挖出的部分必须是规则的矩阵形状,你可以称这一部分为子矩阵。
例如原矩阵
1 2 3
4 5 6
其中
1 2
4 5
是它的子矩阵,但
1 3
4 6
不是
题目描述
给你一个 的矩阵 ,每个位置的值为 ,现在你要从整个矩阵中选择一个 的子矩阵,请你求出最大的子矩阵的和。
输入格式
第一行输入两个空格隔开的整数
接下来 行每行 个空格隔开的数字。
最后输入两个空格空格隔开的整数
输出格式
输出最大的 的和。
3 4
1 2 3 4
5 6 7 8
9 10 11 12
1 2
23
提示
样例一解释
在 的矩阵中,我们需要选择一个 的子矩阵,且和最大,很明显选择右下角 这个位置构成的子矩阵,它的和为
对于所有的数据范围满足 ,,
相关
在下列比赛中: