#### Maximum sum rectangle in a 2D matrix using divide and conquer

I need to implement a maximum sum algorithm that uses the divide and conquer strategy on a 2D matrix. I’m familiar with the brute force approach which runs in O(n^6) time and Kadane’s algorithm which runs in O(n^3) but how would one go about implementing a divide and conquer approach? I’ve been thinking about it all day and nothing comes to mind. In order to provide context, the brute force solution is this:

``````void maxSumBruteForce() {
vector<vector<int>> matrix = genRandomMatrix();
int maxSum = INT_MIN;
printMatrix(matrix);

for (int startRow = 0; startRow < matrix.size(); ++startRow) {
for (int startCol = 0; startCol < matrix.size(); ++startCol) {
for (int endRow = startRow; endRow < matrix.size(); ++endRow) {
for (int endCol = startCol; endCol < matrix.size(); ++endCol) {
int curSum = 0;
for (int row = startRow; row <= endRow; ++row) {
for (int col = startCol; col <= endCol; ++col) {
curSum += matrix[row][col];
}
}

if (curSum > maxSum)
maxSum = curSum;
}
}
}
}

cout << "MAX SUM: " << maxSum << endl;
}
``````

Kadane’s algorithm can be found here: https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/

I figure the solution would check the four quadrants of the matrix, then various combinations of the middles.

Source: Windows Questions C++