Example: Maximum Sum Rectangle in a 2D Matrix in C++

// 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;
}