C++ Program For Dynamic Programming Set 27 (maximum Sum Rectangle In A 2d Matrix)

Dynamic programming offers efficient ways to solve complex problems by breaking them into simpler subproblems. In this article, you will learn how to find the maximum sum rectangle within a 2D matrix, a classic dynamic programming problem that elegantly utilizes Kadane's algorithm.

Problem Statement

Consider a given 2D matrix of integers. The challenge is to identify a rectangular subregion within this matrix such that the sum of all elements within that subregion is maximized. This problem extends the well-known maximum sum subarray problem to two dimensions, where the goal is to find the contiguous subarray with the largest sum. This has practical applications in fields such as image processing (e.g., finding the brightest region in an image), data analysis (e.g., identifying high-value clusters in financial data), and bioinformatics.

Example

Let's consider the following 2D matrix:

{{1,   2,  -1,  -4, -20},
 {-8, -3,   4,   2,   1},
 {3,   8,  10,   1,   3},
 {-4, -1,   1,   7,  -6}}

The maximum sum rectangle in this matrix is:

-3,   4,   2
 8,  10,   1
-1,   1,   7

The sum of elements in this rectangle is 29. The rectangle starts at (row 1, col 1) and ends at (row 3, col 3) (0-indexed).

Background & Knowledge Prerequisites

To effectively understand the solution, a basic understanding of the following concepts is helpful:

• C++ Basics: Familiarity with C++ syntax, loops, arrays (vectors), and functions.
• Dynamic Programming: The general idea of solving problems by breaking them into overlapping subproblems and storing results to avoid recomputation.
• Kadane's Algorithm: This algorithm efficiently finds the maximum sum of a contiguous subarray within a 1D array. It is a cornerstone for solving the 2D maximum sum rectangle problem. The core idea is to keep track of the maximum sum ending at the current position and the overall maximum sum found so far.

// Basic structure for a Kadane's algorithm implementation
int kadane(const std::vector<int>& arr, int& start, int& finish) {
    int max_so_far = INT_MIN; // Use INT_MIN to handle all negative numbers
    int current_max = 0;
    int current_start = 0;

    start = -1;
    finish = -1;

    for (int i = 0; i < arr.size(); ++i) {
        current_max += arr[i];

        if (current_max > max_so_far) {
            max_so_far = current_max;
            start = current_start;
            finish = i;
        }

        if (current_max < 0) {
            current_max = 0;
            current_start = i + 1;
        }
    }

    // Special case: if all numbers are negative, Kadane's standard logic might
    // return 0 or an incorrect index. We need the largest (least negative) single element.
    if (start == -1) { // This happens if all numbers were negative and current_max never became positive
        max_so_far = arr[0];
        start = 0;
        finish = 0;
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] > max_so_far) {
                max_so_far = arr[i];
                start = i;
                finish = i;
            }
        }
    }
    return max_so_far;
}

Run

Use Cases or Case Studies

The maximum sum rectangle problem finds application in various domains:

• Image Processing: Identifying regions of interest, such as areas with the highest average pixel intensity in medical images or satellite imagery.
• Data Analysis: In financial data (e.g., stock prices over time for multiple assets), finding a period and a subset of assets that yield the maximum cumulative profit.
• Bioinformatics: Analyzing sequences (e.g., DNA or protein sequences) to find segments with the highest scoring regions, which might indicate functional importance.
• Resource Allocation: Optimizing resource distribution over a grid-like structure, where each cell represents a cost or benefit, to find the most profitable region.
• Game Development: For grid-based strategy games, determining optimal areas for building or deploying units based on terrain bonuses or penalties.

Solution Approaches

The most common and efficient solution for the maximum sum rectangle problem leverages dynamic programming by reducing the 2D problem to multiple 1D problems using Kadane's algorithm.

Dynamic Programming with Kadane's Algorithm for Maximum Sum Rectangle

This approach iterates through all possible pairs of top and bottom rows. For each pair, it collapses the columns between these rows into a 1D auxiliary array. Kadane's algorithm is then applied to this 1D array to find the maximum sum subarray, which corresponds to the maximum sum rectangle for the current top and bottom rows.

One-Line Summary

The 2D problem is transformed into multiple 1D maximum sum subarray problems by fixing top and bottom rows and summing elements column-wise, then applying Kadane's algorithm.

Code Example

// Maximum Sum Rectangle in a 2D Matrix
#include <iostream>
#include <vector>
#include <climits> // For INT_MIN
#include <algorithm> // For std::fill

using namespace std;

// Kadane's algorithm to find maximum sum subarray in a 1D array
// It also returns the start and end indices of the maximum sum subarray.
int kadane(const vector<int>& arr, int& start, int& finish) {
    int max_so_far = INT_MIN;
    int current_max = 0;
    int current_start = 0;

    start = -1;
    finish = -1;

    // Standard Kadane's algorithm
    for (int i = 0; i < arr.size(); ++i) {
        current_max += arr[i];

        if (current_max > max_so_far) {
            max_so_far = current_max;
            start = current_start;
            finish = i;
        }

        if (current_max < 0) {
            current_max = 0;
            current_start = i + 1;
        }
    }

    // Special case: If all numbers in the array are negative,
    // the above Kadane's will incorrectly return 0 as max_so_far
    // or indices that don't correspond to the actual largest negative sum.
    // We need to find the largest (least negative) single element in this scenario.
    if (start == -1 || max_so_far < 0) { // If no positive sum subarray was found, or max_so_far is negative
        max_so_far = arr[0];
        start = 0;
        finish = 0;
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] > max_so_far) {
                max_so_far = arr[i];
                start = i;
                finish = i;
            }
        }
    }
    return max_so_far;
}

// Function to find the maximum sum rectangle in a 2D matrix
void findMaxSum(const vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) {
        cout << "Matrix is empty." << endl;
        return;
    }
    int cols = matrix[0].size();
    if (cols == 0) {
        cout << "Matrix has empty rows." << endl;
        return;
    }

    int max_sum = INT_MIN;
    int final_left = -1, final_right = -1, final_top = -1, final_bottom = -1;

    vector<int> temp(cols); // Auxiliary array for Kadane's

    // Iterate over all possible top rows
    for (int top = 0; top < rows; ++top) {
        std::fill(temp.begin(), temp.end(), 0); // Reset temp array for each new top row

        // Iterate over all possible bottom rows (starting from current top row)
        for (int bottom = top; bottom < rows; ++bottom) {
            // Update temp array for current rectangle (from top to bottom row)
            // Sum elements column-wise between 'top' and 'bottom' rows
            for (int col = 0; col < cols; ++col) {
                temp[col] += matrix[bottom][col];
            }

            // Apply Kadane's algorithm to the current temp array (1D array of column sums)
            int current_start_col, current_end_col;
            int sum = kadane(temp, current_start_col, current_end_col);

            // Update overall maximum sum if current sum is greater
            if (sum > max_sum) {
                max_sum = sum;
                final_left = current_start_col;
                final_right = current_end_col;
                final_top = top;
                final_bottom = bottom;
            }
        }
    }

    // Output the result
    cout << "Maximum sum is: " << max_sum << endl;
    cout << "Rectangle coordinates (0-indexed):" << endl;
    cout << "  Top-Left: (" << final_top << ", " << final_left << ")" << endl;
    cout << "  Bottom-Right: (" << final_bottom << ", " << final_right << ")" << endl;

    cout << "\\nThe sub-rectangle with maximum sum is:" << endl;
    for (int i = final_top; i <= final_bottom; ++i) {
        for (int j = final_left; j <= final_right; ++j) {
            cout << matrix[i][j] << "\\t";
        }
        cout << endl;
    }
}

int main() {
    // Step 1: Define the 2D matrix
    vector<vector<int>> matrix = {
        {1, 2, -1, -4, -20},
        {-8, -3, 4, 2, 1},
        {3, 8, 10, 1, 3},
        {-4, -1, 1, 7, -6}
    };

    // Step 2: Call the function to find the maximum sum rectangle
    cout << "Processing Matrix 1:" << endl;
    findMaxSum(matrix);
    cout << "\\n------------------------------------------------\\n" << endl;

    // Another example with all negative numbers
    vector<vector<int>> matrix2 = {
        {-1, -2, -3},
        {-4, -5, -6},
        {-7, -8, -9}
    };
    cout << "Processing Matrix 2 (all negative numbers):" << endl;
    findMaxSum(matrix2);
    cout << "\\n------------------------------------------------\\n" << endl;

    // Example with a single row
    vector<vector<int>> matrix3 = {
        {-1, 5, -2, 8, -10}
    };
    cout << "Processing Matrix 3 (single row):" << endl;
    findMaxSum(matrix3);

    return 0;
}

Run

Sample Output

Processing Matrix 1:
Maximum sum is: 29
Rectangle coordinates (0-indexed):
  Top-Left: (1, 1)
  Bottom-Right: (3, 3)

The sub-rectangle with maximum sum is:
-3      4       2
8       10      1
-1      1       7

------------------------------------------------

Processing Matrix 2 (all negative numbers):
Maximum sum is: -1
Rectangle coordinates (0-indexed):
  Top-Left: (0, 0)
  Bottom-Right: (0, 0)

The sub-rectangle with maximum sum is:
-1

------------------------------------------------

Processing Matrix 3 (single row):
Maximum sum is: 11
Rectangle coordinates (0-indexed):
  Top-Left: (0, 1)
  Bottom-Right: (0, 3)

The sub-rectangle with maximum sum is:
5       -2      8

Stepwise Explanation

1. Initialization:

• Initialize max_sum to INT_MIN to correctly handle cases with negative numbers.
• Store the coordinates of the maximum sum rectangle (final_left, final_right, final_top, final_bottom).
• Create a 1D auxiliary array temp of size cols, initialized to zeros. This array will store the sum of elements for each column between the current top and bottom rows.

1. Iterate through Top Rows:

• Use an outer loop to fix the top row, from 0 to rows - 1.
• For each new top row, reset the temp array to all zeros using std::fill.

1. Iterate through Bottom Rows:

• Use a nested loop to fix the bottom row, from the current top row to rows - 1. This ensures bottom is always greater than or equal to top.

1. Update Auxiliary Array:

• For the current pair of (top, bottom) rows, iterate through each col from 0 to cols - 1.
• Add matrix[bottom][col] to temp[col]. This accumulates the sum of elements in each column from top to bottom. At this point, temp represents a 1D array where each element temp[j] is the sum of matrix[i][j] for i from top to bottom.

1. Apply Kadane's Algorithm:

• Call the kadane function on the temp array. This returns the maximum sum sum for the current 1D array, along with its current_start_col and current_end_col.
• The kadane function is crucial here; it finds the best contiguous column range for the currently fixed row span.

1. Update Global Maximum:

• If the sum returned by Kadane's is greater than max_sum, update max_sum with sum.
• Also, update final_left, final_right, final_top, and final_bottom with the coordinates corresponding to this new maximum sum rectangle.

1. Output: After checking all possible (top, bottom) row pairs, print the max_sum and the coordinates of the rectangle that achieves this sum.

The time complexity of this approach is O(rows \* rows \* cols), where rows is the number of rows and cols is the number of columns. This is because there are O(rows \* rows) pairs of (top, bottom) rows, and for each pair, we iterate through cols to update temp and then apply Kadane's algorithm, which takes O(cols) time.

Conclusion

The maximum sum rectangle problem demonstrates a powerful technique in dynamic programming: reducing a higher-dimensional problem to a series of lower-dimensional subproblems. By strategically fixing two dimensions (top and bottom rows) and applying Kadane's algorithm to the accumulated column sums, we efficiently find the optimal rectangular subregion. This method highlights the versatility of Kadane's algorithm beyond 1D arrays and its importance in solving more complex problems.

Summary

• Problem: Find the sub-rectangle with the maximum sum in a 2D matrix.
• Key Idea: Convert the 2D problem into a series of 1D maximum sum subarray problems.
• Algorithm:

1. Iterate through all possible top rows.
2. For each top row, iterate through all possible bottom rows (from top to rows-1).
3. Between top and bottom rows, create a temporary 1D array (temp) by summing elements column-wise.
4. Apply Kadane's Algorithm to this temp array to find the maximum sum subarray and its column boundaries.
5. Update the global maximum sum and corresponding rectangle coordinates if a larger sum is found.

• Prerequisite: A solid understanding of Kadane's Algorithm.
• Time Complexity: O(rows \* rows \* cols).
• Applications: Image processing, data analysis, bioinformatics, financial modeling.