Maximum Submatrix

head file

#pragma once
typedef struct {
	int max_value;
	int startPoint;
	int endPoint;
}sSequenceMax;

typedef struct {
	int max_value;
	int startRow;
	int startCol;
	int endRow;
	int endCol;
}sMatrixMax;

source file

#include <iostream>		// system head file <> without suffix
#include <iomanip>
#include "maxMatSeq.h"	// project head file "" with suffix

using namespace std;

#define MIN_VALUE (-2147483647)
#define MATRIX_ROW (4)
#define MATRIX_COL (4)

sSequenceMax maxSubSequence(int* A, int length);
sMatrixMax maxSubMatrix(int** A, int row, int col);

// maxium sub-matrix
int matrixPool[MATRIX_ROW][MATRIX_COL] = {	{ 0, -2, -7,  0},
											{ 9,  2, -6,  2},
											{-4,  1, -4,  1},
											{-1,  8,  0, -2}
										 };
int testMatrix[4] = {4, 11, -10, 1};

int main() {
	sMatrixMax str_MatMax;
	sSequenceMax str_SeqMax;
	int maximum = MIN_VALUE;
	// create dynamic 2-dimensional array
	int ** matrix = new int*[MATRIX_ROW];
	for (int i = 0; i < MATRIX_ROW; i++) {
		*(matrix + i) = new int[MATRIX_COL];
	}
	for (int i = 0; i < MATRIX_ROW; i++) {
		for (int j = 0; j < MATRIX_COL; j++) {
			*(*(matrix + i) + j) = matrixPool[i][j];
		}
	}
	str_SeqMax = maxSubSequence(testMatrix, 4);
	cout << str_SeqMax.max_value << ' ' << str_SeqMax.startPoint << ' ' << str_SeqMax.endPoint << endl;
	str_MatMax = maxSubMatrix(matrix, MATRIX_ROW, MATRIX_COL);
	cout << str_MatMax.max_value << ' ' << str_MatMax.startRow << ' ' << str_MatMax.startCol << ' ' << str_MatMax.endRow << ' ' << str_MatMax.endCol;
	return maximum;
}

sMatrixMax maxSubMatrix(int** A, int row, int col) {
	sSequenceMax str_SeqMax;
	sMatrixMax str_MatMax;
	int maximum = MIN_VALUE;
	str_MatMax.max_value = MIN_VALUE;
	str_MatMax.startRow		= -1;
	str_MatMax.endRow		= -1;
	str_MatMax.startCol		= -1;
	str_MatMax.endCol		= -1;
	// create dynamic 2-dimensonal array
	int** totalSum = new int*[MATRIX_ROW + 1];
	int* subarrayColSum = new int[MATRIX_COL];
	for (int i = 0; i < MATRIX_ROW + 1; i++) {
		*(totalSum + i) = new int[MATRIX_COL];
	}
	
	cout << "######## The total array is: ########" << endl;
	for (int j = 0; j < MATRIX_COL; j++) {
		*(*(totalSum)+j) = 0;
		cout << setw(5) << *(*(totalSum)+j) << ' ';
	}
	cout << endl;
	for (int i = 1; i < MATRIX_ROW + 1; i++) {
		for (int j = 0; j < MATRIX_COL; j++) {
			*(*(totalSum + i) + j) = *(*(totalSum + i - 1) + j) + A[i - 1][j];
			cout << setw(5) << *(*(totalSum + i) + j) << ' ';
		}
		cout << endl;
	}
	cout << "######## End of total array  #########" << endl;


	for (int i = 1; i <= MATRIX_ROW; i++) { // i denotes the row of possible maximum subarray
		for (int j = 0; j <= MATRIX_ROW - i; j++) { // check all of the possible maximum subarray according to i
			cout << "testMatrix: row from " << j << ", no. of rows = " << i << endl;
			for (int t = 0; t < MATRIX_COL; t++) { // caculate column of subarray that start from row j with i rows
				*(subarrayColSum + t) = *(*(totalSum + j + i) + t) - *(*(totalSum + j) + t);
				cout << *(subarrayColSum + t) << ' ';
			}
			cout << endl;
			str_SeqMax = maxSubSequence(subarrayColSum, MATRIX_COL);
			if (str_SeqMax.max_value > str_MatMax.max_value) {
				str_MatMax.max_value = str_SeqMax.max_value;
				str_MatMax.startRow = j;
				str_MatMax.endRow = j + i - 1;
				str_MatMax.startCol = str_SeqMax.startPoint;
				str_MatMax.endCol = str_SeqMax.endPoint;
			}
		}
	}
	return str_MatMax;
}

sSequenceMax maxSubSequence(int* A, int length) {
	sSequenceMax str_SeqMax;
	int maximum = MIN_VALUE;
	int startPoint = -1;
	int endPoint = -1;
	int tempSum = 0;
	int* temp = new int[length + 1];
	*temp = 0;
	// find maximum and end point of the maximum subarray
	for (int i = 0; i < length; i++) {
		*(temp + i + 1) = *(temp + i) > 0 ? *(temp + i) + A[i] : A[i];
		if (*(temp + i + 1) > maximum) {
			maximum = *(temp + i + 1);
			endPoint = i;
		}
	}
	// find start point of the maximum subarray
	for (int i = endPoint; i >= 0; i--) {
		tempSum += A[i];
		if (tempSum == maximum) {
			startPoint = i;
			break;
		}
	}
	str_SeqMax.max_value = maximum;
	str_SeqMax.startPoint = startPoint;
	str_SeqMax.endPoint = endPoint;
	return str_SeqMax;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

20 − 3 =

47 + = 52