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

user_3308219 0
Viewed 478

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.

algorithm c++
1 Answers

One way to adapt the article1 David Eisenstat shared in the comments could be the following:

If we divide the rectangle in two,

 -------------------
|         |         |
|         |         |
|   A     |    B    |
|         |         |
|         |         |
 -------------------

either the max sum is in A or it's in B or it's in a rectangle that has a part in A and a part in B. To calculate the latter, we use from each side total_sum, max_sum, max_prefix, max_suffix, for each O(num_rows^2) row bounds.

        A
 ---------------
|               |
|-----row_i-----|
|               |
|<--total_sum-->|
|               |
|max_pfx--|     |
|     |--max_sfx|
|               |
|-----row_j-----|
|               |
|               |
 ---------------

Then for each window of rows row_i to row_j, from A and B we have:

total_sum_AB = total_sum_A + total_sum_B
max_prefix_AB = max(max_prefix_A, total_sum_A + max_prefix_B)
max_suffix_AB = max(max_suffix_B, max_suffix_A + total_sum_B)
max_sum_AB = max(max_sum_A, max_sum_B, max_suffix_A + max_prefix_B)

Python code:

def g(M, num_rows, l, r):
  dp = [[None] * num_rows for _ in range(num_rows)]

  if l == r:
    for i in range(num_rows):
      dp[i][i] = [M[i][l], M[i][l], M[i][l], M[i][l]]

      for j in range(i+1, num_rows):
        dp[i][j] = [M[j][l] + dp[i][j-1][0], M[j][l] + dp[i][j-1][1], M[j][l] + dp[i][j-1][2], M[j][l] + dp[i][j-1][3]]

    return dp

  mid = l + (r - l) // 2

  dp_l = g(M, num_rows, l, mid)
  dp_r = g(M, num_rows, mid + 1, r)

  for i in range(num_rows):
    for j in range(i, num_rows):
      [total_sum_l, max_sum_l, max_pfx_l, max_sfx_l] = dp_l[i][j]
      [total_sum_r, max_sum_r, max_pfx_r, max_sfx_r] = dp_r[i][j]

      total_sum = total_sum_l + total_sum_r
      max_pfx = max(max_pfx_l, total_sum_l + max_pfx_r)
      max_sfx = max(max_sfx_r, total_sum_r + max_sfx_l)
      max_sum = max(max_sum_l, max_sum_r, max_sfx_l + max_pfx_r)

      dp[i][j] = [total_sum, max_sum, max_pfx, max_sfx]

  return dp


def f(M):
  num_rows = len(M)

  dp = g(M, num_rows, 0, len(M[0]) - 1)

  best = -float('inf')

  for i in range(num_rows):
    for j in range(i, num_rows):
      [total_sum, max_sum, max_pfx, max_sfx] = dp[i][j]
      best = max(best, max_sum, max_pfx, max_sfx)

  return best

Output:

M = [
  [ 1,  2, -1, -4,-20],
  [-8, -3,  4,  2,  1],
  [ 3,  8, 10,  1,  3],
  [-4, -1,  1,  7, -6]
]

print(f(M)) # 29

"""
  [ 1,  2, -1, -4,-20],
       -----------
  [-8,| -3,  4,  2,|  1],
  [ 3,|  8, 10,  1,|  3],
  [-4,| -1,  1,  7,| -6]
       -----------
"""

1 Divide & Conquer strikes back: maximum-subarray in linear time (Ovidiu Daescu and Shane St. Luce, Department of Computer Science, University of Texas at Dallas)

user_20347870
Related