解题思路:
二维压缩成一维的最大子段,枚举。
参考代码:
#include<bits/stdc++.h> #define Inf 0x3F3F3F3F using namespace std; const int SIZE = 502; int datas[SIZE][SIZE]; int main() { int M, N, tmp; scanf("%d%d", &M, &N); for (int i1 = 1; i1 <= M; i1++) for (int i2 = 1; i2 <= N; i2++) { scanf("%d", &tmp); datas[i1][i2] = datas[i1 - 1][i2] + tmp; } int ans = -Inf, nowValue; for (int line = 1; line <= M; line++) { for (int D = line; D <= M; D++) { int tmp = -Inf; for (int pos = 1; pos <= N; pos++){ nowValue = datas[D][pos] - datas[line - 1][pos]; tmp = max(tmp + nowValue, nowValue); if (tmp > ans) ans = tmp; } } } cout << ans; }
0.0分
0 人评分