/* Example:
 * 41  17  47
 * 33 -16 -16
 * 26 -30  36
 * -3 -18 -19
 * Max submatrix sum: 138
 * Start (0, 2)
 * End   (0, 2)
 * 41  17  47
 * 33 -16 -16
 * 26 -30  36
 */
#include <iostream>
#include <iomanip>
#include <ctime>
#include <array>

template <typename ElemType, size_t Row, size_t Column>
using Matrix = std::array<std::array<ElemType, Column>, Row>;

template <typename Matrix>
using StorageType = typename Matrix::value_type::value_type;

template <typename Matrix>
auto getSubmatrixSum(const Matrix& matrix, size_t startX, size_t endX, size_t startY, size_t endY) {
	StorageType<Matrix> sum{ 0 };
	for (size_t x = startX; x <= endX; ++x) {
		for (size_t y = startY; y <= endY; ++y) {
			sum += matrix[x][y];
		}
	}
	return sum;
}

template <typename Matrix>
void generateRandomMatrix(Matrix& matrix) {
	// Инициализируем генератор псевдослучайных чисел
	std::srand(unsigned(std::time(0)));

	for (size_t x = 0U; x < matrix.size(); x++) {
		for (size_t y = 0U; y < matrix[x].size(); y++) {
			matrix[x][y] = std::rand() % 100 - 50;
		}
	}
}

int main() {
	constexpr size_t rowCount = 4U;
	constexpr size_t colCount = 3U;

	using ElemType = float;

	Matrix<ElemType, rowCount, colCount> matrix;
	generateRandomMatrix(matrix);

	// Выводим матрицу
	for (size_t x = 0U; x < rowCount; ++x) {
		for (size_t y = 0U; y < colCount; ++y) {
			std::cout << std::setw(3) << matrix[x][y] << " ";
		}
		std::cout << std::endl;
	}

	// Храним данные о максимальной сумме
	struct {
		ElemType sum = std::numeric_limits<ElemType>::min();
		size_t startX;
		size_t startY;
		size_t endX;
		size_t endY;
	} submatrix;

	// Перемещаем 'начальную' клетку
	for (size_t startX = 0U; startX < rowCount; ++startX) {
		for (size_t startY = 0U; startY < colCount; ++startY) {

			// Перемещаем конечную клетку
			for (size_t endX = rowCount - 1U;; --endX) {
				for (size_t endY = colCount - 1U;; endY--) {
					// Считаем сумму текущей подматрицы
					ElemType sum = getSubmatrixSum(matrix, startX, endX, startY, endY);

					// Если сумма элементов текущей подматрицы больше, то сохраняем 
					if (sum > submatrix.sum) {
						submatrix.sum = sum;
						submatrix.startX = startX;
						submatrix.startY = startY;
						submatrix.endX = endX;
						submatrix.endY = endY;
					}
					if (endY == startY) break;
				}
				if (endX == startX) break;
			}
		}
	}

	std::cout << "Max submatrix sum: " << submatrix.sum << std::endl;
	std::cout << "Start (" << submatrix.startX << ", " << submatrix.endX << ")" << std::endl;
	std::cout << "End   (" << submatrix.startY << ", " << submatrix.endY << ")" << std::endl;

	// Выводим подматрицу
	for (size_t x = submatrix.startX; x <= submatrix.endX; ++x) {
		for (size_t y = submatrix.startY; y <= submatrix.endY; ++y) {
			std::cout << std::setw(3) << matrix[x][y] << " ";
		}
		std::cout << std::endl;
	}

	system("pause");
}