本文部分借鉴源于大佬的博客：
现在有一个问题，有一个一维数组，求它的最大区间和。
我们可以利用贪心的思想，先将这个数组前缀和处理，所以我们可以得到区间和为 sum[L—R] = sum[R] - sum[L-1]；因此，我们可以一边枚举R一边去找最小值，取这个区间和去和答案判断找到最大区间和。
1 int FindSum() 2 { 3 int maxn = 0; 4 int minst = inf; 5 for (int i = 1; i <= n; i++) 6 { 7 minst = min(minst, sum[i - 1]); 8 maxn = max(maxn, sum[i] - minst); 9 }10 return maxn;11 }
我们现在去求二维矩阵的最大子矩阵和。
我们先将矩阵进行预处理，将它的每个列存到一个前缀和二维数组f[i][j]里，这样的话我们只需要枚举起始和终止的行，在这个区间去进行降维为一维去求最大和就可以将时间复杂度变为O(n^3)。
像上图，我们只需要将i-j之间的矩阵降维到一维，(具体操作是你之前预处理列的前缀和数组f[i-j][k]=f[j][k]-f[i-1][k] ,将f数组降维到一维，求最大区间和)，便求出了最大矩阵和。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn = 4e2 + 5; 8 const int INF = 0x3f3f3f3f; 9 int n, ans = -INF;10 int a[maxn][maxn], f[maxn][maxn]; //f[i][j]关于第j列到第i行的列前缀和 11 void init(const int& n)12 {13 for(int i = 1; i <= n; ++i)14 for(int j = 1; j <= n; ++j)15 f[i][j] = f[i - 1][j] + a[i][j]; //求一列的和 16 }17 int b[maxn], sum[maxn]; //降维后的数组 18 int main()19 {20 scanf("%d", &n);21 for(int i = 1; i <= n; ++i)22 for(int j = 1; j <= n; ++j)23 scanf("%d", &a[i][j]);24 init(n);25 for(int i = 1; i <= n; ++i)26 for(int j = i; j <= n; ++j)27 {28 for(int k = 1; k <= n; ++k) b[k] = f[j][k] - f[i - 1][k]; //降维 29 for(int k = 1; k <= n; ++k) sum[k] = sum[k - 1] + b[k]; //求一维前缀和 30 int Min = INF; 31 for(int k = 1; k <= n; ++k)32 {33 Min = min(Min, sum[k - 1]);34 ans = max(ans, sum[k] - Min);35 }36 }37 printf("%d\n", ans);38 return 0;39 }
我们现在看一道例题hdu1559。
题目大意：
给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。这道题n,m<1000，所以我们考虑一下我们只要求固定的子矩阵x,y。
我们只要枚举矩阵起始行，结束行也就是i+x,在进行降维找到最大子矩阵和就ok了，这样的时间复杂度也降到了O(n^2),是不是很简单。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define maxx 110000 8 typedef long long ll; 9 const int inf = 0x3f3f3f3f;10 int a[1010][1010];11 int sum[1010];12 int f[1010][1010];13 int b[1010];14 int n, m;15 16 void init()17 {18 for (int i = 1; i <= n; i++)19 {20 for (int j = 1; j <= m; j++)21 {22 f[i][j] = f[i - 1][j] + a[i][j];23 }24 }25 }26 27 int main()28 {29 int T;30 cin >> T;31 while (T--)32 {33 memset(f, 0, sizeof(f));34 int x, y;35 cin >> n >> m >> x >> y;36 for (int i = 1; i <= n; i++)37 {38 for (int j = 1; j <= m; j++)39 {40 cin >> a[i][j];41 }42 }43 init();44 int maxn = 0;45 for (int i = 1; i <= n; i++)46 {47 memset(sum, 0, sizeof(sum));48 memset(b, 0, sizeof(b));49 int j = i + x - 1;50 for (int k = 1; k <= m; k++)51 b[k] = f[j][k] - f[i - 1][k];52 for (int k = 1; k <= m; k++)53 sum[k] = sum[k - 1] + b[k];54 for (int k = 1; k + y <= m + 1; k++)55 {56 maxn = max(maxn, sum[k + y - 1] - sum[k - 1]);57 }58 }59 cout << maxn << endl;60 }61 return 0;62 }