编程求二维数组(矩阵)的子矩阵之和的最大值。
#include
#include
using namespace std;
#define MAXN 1003
int A[MAXN][MAXN];
long long PS[MAXN][MAXN];
inline long long MatrixSum(int s, int t, int i, int j)
{
return PS[i][j] - PS[i][t - 1] - PS[s - 1][j] + PS[s - 1][t - 1];
}
int main()
{
int m, n, i, j;
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin >> A[i][j];
for (i = 0; i <= n; i++)
PS[i][0] = 0;
for (j = 0; j <= m; j++)
PS[0][j] = 0;
// 计算矩阵的部分和
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
PS[i][j] = A[i][j] + PS[i - 1][j] + PS[i][j - 1] - PS[i - 1][j - 1];
int a, c;
long long All = A[1][1];
for (a = 1; a <= n; a++)
for (c = a; c <= n; c++)
{
// 将子矩阵上下边界设为第a行和第c行,在这些子矩阵中取最大值
long long Tail = MatrixSum(a, 1, c, 1);
for (j = 2; j <= m; j++)
{
Tail = max(MatrixSum(a, j, c, j),
MatrixSum(a, j, c, j) + Tail);
All = max(Tail, All);
}
}
cout << All;
}