C++ 最大子矩形问题

最大子矩形问题是在一个二维矩阵中寻找一个子矩形，使得该子矩形内所有元素的和最大。这是一个经典的动态规划问题。

问题描述

给定一个 m × n 的整数矩阵，找出其中和最大的子矩形。

解决方案

方法一：暴力解法（时间复杂度 O(m²n²)）

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSubRectangle(vector<vector<int>>& matrix) {
    int m = matrix.size();
    if (m == 0) return 0;
    int n = matrix[0].size();
    
    int maxSum = INT_MIN;
    
    // 遍历所有可能的子矩形
    for (int top = 0; top < m; top++) {
        for (int bottom = top; bottom < m; bottom++) {
            for (int left = 0; left < n; left++) {
                for (int right = left; right < n; right++) {
                    // 计算当前子矩形的和
                    int sum = 0;
                    for (int i = top; i <= bottom; i++) {
                        for (int j = left; j <= right; j++) {
                            sum += matrix[i][j];
                        }
                    }
                    maxSum = max(maxSum, sum);
                }
            }
        }
    }
    
    return maxSum;
}

方法二：优化解法（时间复杂度 O(m²n)）

使用 Kadane 算法的二维扩展：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSubRectangle(vector<vector<int>>& matrix) {
    int m = matrix.size();
    if (m == 0) return 0;
    int n = matrix[0].size();
    
    int maxSum = INT_MIN;
    
    // 遍历所有可能的行对 (top, bottom)
    for (int top = 0; top < m; top++) {
        vector<int> temp(n, 0);
        
        for (int bottom = top; bottom < m; bottom++) {
            // 将当前行对之间的列求和，转换为一维数组
            for (int j = 0; j < n; j++) {
                temp[j] += matrix[bottom][j];
            }
            
            // 在一维数组上使用 Kadane 算法
            int currentSum = 0;
            int maxCurrent = INT_MIN;
            
            for (int j = 0; j < n; j++) {
                currentSum = max(temp[j], currentSum + temp[j]);
                maxCurrent = max(maxCurrent, currentSum);
            }
            
            maxSum = max(maxSum, maxCurrent);
        }
    }
    
    return maxSum;
}

方法三：完整实现（包含边界处理）

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class MaxSubRectangle {
public:
    // 方法1：暴力解法
    static int bruteForce(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        
        int m = matrix.size(), n = matrix[0].size();
        int maxSum = INT_MIN;
        
        for (int top = 0; top < m; top++) {
            for (int left = 0; left < n; left++) {
                vector<int> colSum(n, 0);
                
                for (int bottom = top; bottom < m; bottom++) {
                    for (int right = left; right < n; right++) {
                        colSum[right] += matrix[bottom][right];
                        
                        int sum = 0;
                        for (int k = left; k <= right; k++) {
                            sum += colSum[k];
                        }
                        maxSum = max(maxSum, sum);
                    }
                }
            }
        }
        
        return maxSum;
    }
    
    // 方法2：优化解法
    static int optimized(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        
        int m = matrix.size(), n = matrix[0].size();
        int maxSum = INT_MIN;
        
        for (int top = 0; top < m; top++) {
            vector<int> colSum(n, 0);
            
            for (int bottom = top; bottom < m; bottom++) {
                // 更新列和
                for (int j = 0; j < n; j++) {
                    colSum[j] += matrix[bottom][j];
                }
                
                // 使用 Kadane 算法找最大子数组和
                int currentSum = 0;
                for (int j = 0; j < n; j++) {
                    currentSum = max(colSum[j], currentSum + colSum[j]);
                    maxSum = max(maxSum, currentSum);
                }
            }
        }
        
        return maxSum;
    }
    
    // 方法3：返回最大子矩形的位置信息
    static vector<int> findMaxSubRectangle(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {0, 0, 0, 0, 0};
        
        int m = matrix.size(), n = matrix[0].size();
        int maxSum = INT_MIN;
        vector<int> result(5); // top, left, bottom, right, maxSum
        
        for (int top = 0; top < m; top++) {
            vector<int> colSum(n, 0);
            
            for (int bottom = top; bottom < m; bottom++) {
                // 更新列和
                for (int j = 0; j < n; j++) {
                    colSum[j] += matrix[bottom][j];
                }
                
                // 使用 Kadane 算法
                int currentSum = 0;
                int start = 0;
                int maxCurrent = INT_MIN;
                int tempStart = 0, tempEnd = 0;
                
                for (int j = 0; j < n; j++) {
                    if (currentSum <= 0) {
                        currentSum = colSum[j];
                        tempStart = j;
                    } else {
                        currentSum += colSum[j];
                    }
                    
                    if (currentSum > maxCurrent) {
                        maxCurrent = currentSum;
                        tempEnd = j;
                        start = tempStart;
                    }
                }
                
                if (maxCurrent > maxSum) {
                    maxSum = maxCurrent;
                    result[0] = top;
                    result[1] = start;
                    result[2] = bottom;
                    result[3] = tempEnd;
                    result[4] = maxSum;
                }
            }
        }
        
        return result;
    }
};

// 测试函数
int main() {
    vector<vector<int>> matrix = {
        {1, 2, -1, -4, -20},
        {-8, -3, 4, 2, 1},
        {3, 8, 10, 1, 3},
        {-4, -1, 1, 7, -6}
    };
    
    cout << "暴力解法结果: " << MaxSubRectangle::bruteForce(matrix) << endl;
    cout << "优化解法结果: " << MaxSubRectangle::optimized(matrix) << endl;
    
    vector<int> rect = MaxSubRectangle::findMaxSubRectangle(matrix);
    cout << "最大子矩形位置: (" << rect[0] << ", " << rect[1] << ") 到 (" 
         << rect[2] << ", " << rect[3] << ")" << endl;
    cout << "最大和: " << rect[4] << endl;
    
    return 0;
}

算法分析

时间复杂度

• 暴力解法: O(m²n²)
• 优化解法: O(m²n)

空间复杂度

• 暴力解法: O(1)
• 优化解法: O(n)

应用场景

最大子矩形问题在以下领域有广泛应用：

1. 图像处理中的最大亮区检测
2. 数据挖掘中的最大密度区域发现
3. 计算机视觉中的目标检测
4. 基因组学中的基因表达分析

扩展变种

1. 最大正方形问题: 寻找和最大的正方形子矩阵
2. 最大空矩形问题: 在0-1矩阵中寻找最大的全0子矩形
3. 带约束的最大子矩形: 在满足特定条件下的最大子矩形

这个问题的核心思想是将二维问题通过列求和转化为一维问题，然后使用 Kadane 算法高效求解。