プログラミングの美2.15二次元配列の最も大きいサブ配列の和(配列の下付きは(1,1)から始まる)

まず、私たちはこの文章のテーマを見て、私たちは前のテーマ--連続サブ配列の最大と問題を考えます.この問題は間違いなく元の問題を2次元に拡張した場合だ.
この問題を考えるのも難しくありません.1次元マトリクスの考えを解くことができます.つまり、行(または列)を固定することができ、その後、列(または行)が構成する最大和を解くことができます.
ここでの解法は固定行を利用して、それから探す列の和を解いて、本の中の1つの公式を利用します:
左上隅の要素(1,1)と現在の要素(i,j)を頂点対とするサブマトリクスの部分和,部分和の計算は以下の通りである.
PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]
これにより、次のような答えが簡単に得られます.
関数宣言:

/*2.15            (     (1,1)  )*/
int DutPartialSum(int**, int, int, int);
int DutMaxSubMatrixInTwoDimensionArray(int**, int, int);

ソース:

bool _DutPartialSum = false;
int DutPartialSum(int** p, int i, int j, int k)
{
	if (!p || i <= 0 || j <= 0 || k <= 0)
	{
		_DutPartialSum = true;

		return -1;
	}

	return p[j][k] - p[j][k - 1] - p[i - 1][k] + p[i - 1][k - 1];
}

bool _DutMaxSubMatrixInTwoDimensionArray = false;
int DutMaxSubMatrixInTwoDimensionArray(int** A, int n, int m)
{
	if (!A || n <= 0 || m <= 0)
	{
		_DutMaxSubMatrixInTwoDimensionArray = true;

		return -1;
	}

	int **p = new int* [n + 1];
	for (int i = 0; i <= n; ++i)
		p[i] = new int[m];

	for (int i = 0; i <= n; ++i)
		p[i][0] = 0;

	for (int i = 0; i <= m; ++i)
		p[0][i] = 0;

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + A[i][j];

	int maxSum = 1 << 31;

	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; ++j)
		{
			int start = DutPartialSum(p, i, j, m);
			int all = DutPartialSum(p, i, j, m);

			for (int k = m - 1; k >= 1; --k)
			{
				if (start <= 0)
					start = DutPartialSum(p, i, j, k);
				else
					start += DutPartialSum(p, i, j, k);

				if (start > all)
					all = start;
			}

			if (all > maxSum)
				maxSum = all;
		}
	}

	return maxSum;
}