毎日1つのアルゴリズムシリーズ(32)を勉強します(1つのマトリクスの中で最大の2次元マトリクス(要素と最大)を求めます)

タイトル:
1つの行列の中で最大の2次元の行列(要素と最大)を求めます.例えば:1 2 0 3 4 2 4 4 5 1 1 5 3 0の中で最大の2次元行列は:4 5 3
要求:(1)アルゴリズムを書く;(2)分析時間の複雑さ;(3)Cでキーコードを書く.
 
構想1:この問題は最大の2次元行列を要求して、私達のまず思い付く1つの解法は:行1から行Nまで遍歴して、2次元行列を単位として遍歴して、すなわち、(行x列x--行x+1列x+1)は1単位で遍歴し、遍歴の過程でその行列の和値を記録し、最大和値と比較し、最大の2次元行列と値に対応する行列値を遍歴が終わるまで保存し、最大の2次元行列を見つけることができる.Ncolが表す行列の列数.
 
コードは次のとおりです.

/*-----------------------------
Copyright by yuucyf. 2011.08.25
------------------------------*/

#include "stdafx.h"
#include <assert.h>
#include <iostream>
using namespace std;

typedef struct tagMatrixInfo
{
	int i32nLine;
	int i32nCol;
	
	tagMatrixInfo()
	{
		i32nLine = i32nCol = 0;
	}
}S_MatrixInfo;


S_MatrixInfo GetMax2X2Matrix(int **ppMatrix, int nLine, int nCol)
{
	assert(ppMatrix);
	assert(nLine >= 2);
	assert(nCol >= 2);

	S_MatrixInfo sMaxMatrixInfo;

	int nMaxValue = 0, nTempValue = 0;
	for (int i32I = 0; i32I < nLine - 1; i32I++)
	{
		for (int i32J = 0; i32J < nCol - 1; i32J++)
		{
			nTempValue += (ppMatrix[i32I][i32J] + ppMatrix[i32I][i32J+1]); 
			nTempValue += (ppMatrix[i32I+1][i32J] + ppMatrix[i32I+1][i32J+1]);

			if (nTempValue > nMaxValue)
			{
				nMaxValue = nTempValue;
				sMaxMatrixInfo.i32nLine = i32I;
				sMaxMatrixInfo.i32nCol  = i32J;
			}
			nTempValue = 0;
		}
	}

	return sMaxMatrixInfo;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int i32I = 0, i32J = 0;
	int i32nLine = 0, i32nCol = 0;
	cin >> i32nLine >> i32nCol;
	int **ppMatrix = new int *[i32nLine];
	assert(ppMatrix);

	for (i32I = 0; i32I < i32nLine; i32I++)
	{
		ppMatrix[i32I] = new int[i32nCol];
		assert(ppMatrix[i32I]);

		for (i32J = 0; i32J < i32nCol; i32J++)
		{
			cin >> ppMatrix[i32I][i32J];
		}
	}

	S_MatrixInfo sMaxMatrixInfo = GetMax2X2Matrix(ppMatrix, i32nLine, i32nCol);
	cout << endl << "        :" << endl;
	for (i32I = sMaxMatrixInfo.i32nLine; i32I < sMaxMatrixInfo.i32nLine + 2; i32I++)
	{
		for (i32J = sMaxMatrixInfo.i32nCol; i32J < sMaxMatrixInfo.i32nCol + 2; i32J++)
		{
			cout << ppMatrix[i32I][i32J] << " ";
		}
		cout << endl;
	}

         return 0;
}

拡張:もしテーマが最大のサブマトリクスを求めることを要求するならば、私たちはマトリクスの垂直方向の配列を1つの要素と見なすことができます.したがって,行列は我々がよく知っている1次元配列に変換された.すなわち、以上の行列は、a[1->n][1]a[1->n][2]...a[1->n][i] .. a[1->n][j] .. a[1->n][n]1->nは垂直方向を表し、a[1->n][1]は第1列のすべての要素が加算された値を表す.では、5 X 5行列と仮定すると、その解法は、第1行:a[1-5][1]a[1-5][2]a[1-5][3]a[1-5][4]a[1-5][5]が1次元配列を形成し、その配列の最大和値はSum 1である.
2行目:a[2-5][1]a[2-5][2]a[2-5][3]a[2-5][4]a[2-5][5]は、Sum 2の最大和値を有する1次元配列を形成する.
3行目:a[3-5][1]a[3-5][2]a[3-5][3]a[3-5][4]a[3-5][5]は、Sum 3の最大和値を持つ1次元配列を形成する.
4行目:a[4-5][1]a[4-5][2]a[4-5][3]a[4-5][4]a[4-5][5]は1次元配列を形成し、この配列の最大和値はSum 4である.
第5行:a[5][1]a[5][2]a[5][3]a[5][4]a[5][5]は一次元配列を形成し、この配列の最大和値はSum 5である.
次に、Sum 1~Sum 5を比較する最大値が、その行列の最大サブ行列に対応する和であることを見出す.