广告牌设计/seo优化网站词

要求一个二维矩阵的最大子矩阵，首先要会求一维矩阵的最大子矩阵（即一维数组连续最大和）
假设原二维矩阵的最大子矩阵所在的行为i到j

1. 当 i = j 时，则最大子矩阵为第 i 行的连续最大和
2. 当 i != j 时，现在我们已经知道最大子矩阵的行，要求的是其所在的列
   我们把从第 i 行到第 j 行的所有行相加，得到一个只有一行的一维数组，则该一维数组的连续最大和就是最大子矩阵。

这里有个小技巧是，可以先利用一个temp二维数组存储matrix每一行累加的结果，然后只需要执行temp[ j ] [ k ] - temp[ i - 1 ] [ k ]即可实现累加，这样就不需要每次都累加。

#include<iostream>
#include<cstdio>using namespace std;const int N = 100 + 10;int matrix[N][N], temp[N][N], arr[N], dp[N];int MaxSequence(int n){  //求一维数组的最大子序列和int maximum = 0;for(int i = 0; i < n; i++){if(i == 0) dp[i] = arr[i];else dp[i] = max(arr[i], dp[i - 1] + arr[i]);maximum = max(maximum, dp[i]);}return maximum;
}int MaxMatrix(int n){int maximum = 0;for(int i = 0; i < n; i++){for(int j = i; j < n; j++){for(int k = 0; k < n; k++){  //获得一维数组if(i == 0) arr[k] = temp[j][k];else arr[k] = temp[j][k] - temp[i - 1][k];  //求第i行到第j行的累加}maximum = max(maximum, MaxSequence(n));  //累加完之后，更新最大值}}return maximum;
}int main(){int n;while(scanf("%d", &n) != EOF){for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){scanf("%d", &matrix[i][j]);}}for(int i = 0; i < n; i++){  //每一行进行累加得到tempfor(int j = 0; j < n; j++){if(i == 0) temp[i][j] = matrix[i][j];else temp[i][j] = temp[i - 1][j] + matrix[i][j];}}printf("%d\n", MaxMatrix(n));}return 0;
}