时间限制: 1.0s 内存限制: 256.0MB
问题描述
给定一个 n*m 的矩阵 A, 求 A 中的一个非空子矩阵, 使这个子矩阵中的元素和最大.
其中, A 的子矩阵指在 A 中行和列均连续的一块.
输入格式
输入的第一行包含两个整数 n, m, 分别表示矩阵 A 的行数和列数.
接下来 n 行, 每行 m 个整数, 表示矩阵 A.
输出格式
输出一行, 包含一个整数, 表示 A 中最大的子矩阵中的元素和.
样例输入
- 3 3
- -1 -4 3
- 3 4 -1
- -5 -2 8
样例输出
10
样例说明
取最后一列, 和为 10.
数据规模和约定
对于 50% 的数据, 1<=n, m<=50;
对于 100% 的数据, 1<=n, m<=500,A 中每个元素的绝对值不超过 5000.
- #include <iostream>
- using namespace std;
- int main(){
- int dp[501][501] = {0};
- int n, m;
- cin>> n>> m;
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= m; j++){
- int t;
- cin>> t;
- // 每一行存的是与上面行的和 (上面所有行)
- dp[i][j] += dp[i - 1][j] + t;
- }
- }
- int s = 0;
- int max = -99999999;
- for(int i = 1; i <= n; i++){
- for(int j = i; j <= n; j++){
- s = 0;
- for(int k = 1; k <= m; k++){
- s += dp[j][k] - dp[i - 1][k];// 按先按列走, 然后按行数间隔递增的顺序 (最外俩个循环)
- if(s> max){
- max = s;
- }
- if(s < 0){
- s = 0;
- }
- }
- }
- }
- cout << max;
- return 0;
- }
最大子阵
来源: http://www.bubuko.com/infodetail-2996322.html