Maximum Sum Submatrix

• Time : O(nm)
• Space : O(nm)

c++

#include <vector>
using namespace std;

int maximumSumSubmatrix(vector<vector<int>> matrix, int size) {
  int n = matrix.size(), m = matrix[0].size(), res = INT_MIN;
	if(n < size or m < size) return -1;
	vector<vector<int>> prefixMatrix(n + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j<= m; j++) {
			prefixMatrix[i][j] = prefixMatrix[i][j-1] + matrix[i-1][j-1];
		}
		for(int j = 1; j <= m; j++) {
			prefixMatrix[i][j] += prefixMatrix[i-1][j];
		}
	}
	
	for(int i = size; i <= n; i++) {
		for(int j = size; j <= m; j++) {
			res = max(res,
								prefixMatrix[i][j] + prefixMatrix[i-size][j-size]
								- prefixMatrix[i-size][j] - prefixMatrix[i][j-size]
							 );
		}
	}
	
  return res;
}