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

  algorithm, c++

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++

LEAVE A COMMENT