Given an n by m matrix of integers, find the submatrix with the maximum sum. Return the sum, left, right, top, bottom.

max_sum_submatrix.cpp

#include "max_sum_submatrix.h"

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> v = { 4,6,8,3,-233,6,5,-2,83,2,3,6,4 };

	std::vector< std::vector<int> > matirx = {
		{-41,2,-1, 4},
		{8,-3,4,2},
		{3,8,10,-8},
		{-4,-1,1,7}
	};
	
	auto range = max_sum_subarray(v);
	std::cout << "max_add: " << range.value<<" left: " << range.left << " right: " << range.right << std::endl;
	
	range = max_sum_submatrix(matirx);
	std::cout << "max_add: " << range.value << " left: " << range.left << " right: " << range.right 
		<< " top: " << range.top << " bottom: " << range.bottom << std::endl;

	return 0;
}

max_sum_submatrix.h

#pragma once

#ifndef _MAX_SUM
#define _MAX_SUM

#include <vector>
#include <algorithm>

template<typename T>
struct MaxRange
{
	unsigned left = 0, right = 0, top = 0, bottom = 0;
	T value = 0;
};

template<typename T1, typename T2>
MaxRange<T1> max_sum_subarray(const std::vector<T2> & arr) 
{
	T1 endsum = 0;

	MaxRange<T1> range;//if add many unsigned char, the result may be long long

	unsigned endsum_left = 0, n = arr.size();

	for (unsigned i = 0; i < n; ++i)
	{
		if (endsum <= 0)
		{
			endsum_left = i;
			endsum = arr[i];
		}
		else
		{
			endsum += arr[i];
		}


		if (endsum >= range.value)
		{
			range.value = endsum;

			range.left = endsum_left;
			range.right = i + 1;
		}
	}

	return range;
}

template<typename T>
MaxRange<int> max_sum_subarray(const std::vector<T> & arr) 
{
	return max_sum_subarray<int, T>(arr);
}

template<typename T1, typename T2>
MaxRange<T1> max_sum_submatrix(const std::vector< std::vector<T2> >& matrix) 
{

	MaxRange<T1> range;

	unsigned row = matrix.size(), col = 0;
	if (row > 0) col = matrix[0].size();

	std::vector<T1> array(col, 0);

	for (unsigned top = 0; top < row; ++top)
	{
		std::fill(array.begin(), array.end(), 0);

		for (unsigned bottom = top; bottom < row; ++bottom)
		{

			unsigned i = 0;
			for (auto & v : matrix[bottom])
			{
				array[i++] += v;
			}

			auto range_array = max_sum_subarray(array);

			if (range_array.value >= range.value)
			{
				range.value = range_array.value;
				range.top = top;
				range.bottom = bottom + 1;

				range.left = range_array.left;
				range.right = range_array.right;
			}

		}
	}

	return range;
}

template<typename T2>
MaxRange<int> max_sum_submatrix(const std::vector< std::vector<T2> >& matrix)
{
	return max_sum_submatrix<int, T2>(matrix);
}

#endif  //_MAX_SUM

max_sum_submatrix.ipynb