title: Maximum sum rectangle in a 2D matrix using divide and conquer
body: <p>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:</p>
  <pre><code>void maxSumBruteForce() {
      vector&lt;vector&lt;int&gt;&gt; matrix = genRandomMatrix();
      int maxSum = INT_MIN;
      printMatrix(matrix);
  
      for (int startRow = 0; startRow &lt; matrix.size(); ++startRow) {
          for (int startCol = 0; startCol &lt; matrix.size(); ++startCol) {
              for (int endRow = startRow; endRow &lt; matrix.size(); ++endRow) {
                  for (int endCol = startCol; endCol &lt; matrix.size(); ++endCol) {
                      int curSum = 0;
                      for (int row = startRow; row &lt;= endRow; ++row) {
                          for (int col = startCol; col &lt;= endCol; ++col) {
                              curSum += matrix[row][col];
                          }
                      }
  
                      if (curSum &gt; maxSum)
                          maxSum = curSum;
                  }
              }
          }
      }
  
      cout &lt;&lt; &quot;MAX SUM: &quot; &lt;&lt; maxSum &lt;&lt; endl;
  }
  </code></pre>
  <p>Kadane's algorithm can be found here: <a href="https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/</a></p>
  <p>I figure the solution would check the four quadrants of the matrix, then various combinations of the middles.</p>