2.15 子数组之和的最大值(二维)
分析:将二维降低到一维的情况。
代码:
#include <iostream> const int MAXN = 10000; const int INF = 100000000; using namespace std; int B[MAXN][MAXN], PS[MAXN][MAXN]; int n, m; int BC(int first, int last, int liehao) { return PS[last][liehao] - PS[first-1][liehao] - PS[last][liehao-1] + PS[first-1][liehao-1]; } int MaxSum(int n, int m) { int ret = -INF; int Start = 0, All = 0; for(int a = 1; a <= n; ++a) { for(int c = a; c <= n; ++c) { Start = BC(a, c, m); All = BC(a, c, m); for(int i = m-1; i >= 1; --i) { if(Start < 0) Start = 0; Start += BC(a, c, i); if(Start > All) All = Start; } if(All > ret) ret = All; } } return ret; } int main() { cin >> n >> m; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { cin >> B[i][j]; } } //计算二维数组PS,方便后期在O(1)的时间内求出PS[i][j] for(int i = 0; i <= n; ++i) PS[i][0] = 0; for(int i = 0; i <= m; ++i) PS[0][i] = 0; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { PS[i][j] = PS[i][j-1] + PS[i-1][j] - PS[i-1][j-1] + B[i][j]; } } cout << MaxSum(n, m) << endl; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。