思路:由最大子段和的dp算法演变过来,hdu的Max Sum即是求最大子段和的。有了这个一维的算法,现在是二维,那么我们就枚举行即高的所有可能,若r,k表示第r行和第k行(r<=k)那么,高就是k-r+1. 然后计算出高之间的列值总和,保存在一维数组里,然后对这个一维数组用最大子段和的算求出即是answer。
特殊处理所有值全是负数的情况。此时answer为最大的那个负数。
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <algorithm> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define eps 10e-8 const int MAX_ = 510; int p[MAX_][MAX_]; int m, n,k,maxm, sum, maxi; bool flag; int main(){ while(~scanf("%d%d",&n,&m)){ for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){ p[0][j] = 0; scanf("%d",&k); p[i][j] = p[i-1][j] + k; } } maxm = 0;flag = 0;maxi = -5005; for(int i = 1; i <= n; ++i){ for(int j = i ; j <= n; ++j){ sum = 0; for(int r = 1; r <= m; ++r){ k = p[j][r] -p[i-1][r]; //printf("%d ",a[r]); if(sum > 0){sum += k;} else {sum = k; if(!flag && sum > maxi)maxi = sum; } if(sum > maxm){ maxm = sum; flag = 1; } } } } if(!flag){ maxm = maxi; } printf("%d\n",maxm); } return 0; }