基于分治策略的二维矩阵最大和矩形算法实现问题

核心思路 #

分治策略的核心是将大矩阵不断拆分为更小的子矩阵，最终合并结果。最大和矩形仅存在三种可能：

• 完全位于拆分后的左/上子矩阵
• 完全位于拆分后的右/下子矩阵
• 跨拆分中线的矩形

前两种情况通过递归求解，第三种单独计算后取三者最大值即可。该算法平均时间复杂度为O(n² log n)，优于传统*O(n³)*的Kadane优化方案。

实现步骤 #

1. 边界处理：当子矩阵仅含1行/1列时，直接用一维Kadane算法计算最大子数组和，结束递归
2. 选择拆分方向：优先沿当前子矩阵的长边拆分，减少跨边界计算量：行数>列数则水平拆分为上下两部分，否则垂直拆分为左右两部分
3. 递归计算两个子区域的最大矩形和
4. 计算跨中线的最大矩形和：以垂直拆分为例，固定拆分中线为mid_col，逐行计算从中线向左扩展的前缀和、向右扩展的后缀和，将每行的左右和相加得到该行跨中线的和数组，对该数组跑一维Kadane即可得到跨中线的最大矩形和
5. 合并结果：取子区域最大值、跨中线最大值三者的最大值作为当前子矩阵的结果

参考代码 #

暴力解法（原始版本） #

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算法，求数组最大子数组和
int kadane1D(vector<int>& arr) {
    int maxSum = INT_MIN, curSum = 0;
    for (int num : arr) {
        curSum = max(num, curSum + num);
        maxSum = max(maxSum, curSum);
    }
    return maxSum;
}

// 分治递归函数，入参为当前子矩阵的上下左右边界
int maxSumDivideConquer(vector<vector<int>>& matrix, int top, int bottom, int left, int right) {
    // 边界条件：只有一行
    if (top == bottom) {
        vector<int> row;
        for (int col = left; col <= right; ++col) row.push_back(matrix[top][col]);
        return kadane1D(row);
    }
    // 边界条件：只有一列
    if (left == right) {
        vector<int> col;
        for (int row = top; row <= bottom; ++row) col.push_back(matrix[row][left]);
        return kadane1D(col);
    }

    int mid, maxCross;
    // 沿长边拆分
    if (bottom - top > right - left) {
        // 水平拆分，上下两半
        mid = top + (bottom - top) / 2;
        int maxUp = maxSumDivideConquer(matrix, top, mid, left, right);
        int maxDown = maxSumDivideConquer(matrix, mid+1, bottom, left, right);
        // 计算跨水平中线的最大和
        maxCross = INT_MIN;
        // 遍历所有左右边界组合
        for (int l = left; l <= right; ++l) {
            vector<int> sumArr(bottom - top + 1, 0);
            int curSum = 0;
            // 从中线往上累加
            for (int row = mid; row >= top; --row) {
                curSum += matrix[row][l];
                sumArr[row - top] = curSum;
            }
            curSum = 0;
            // 从中线往下累加
            for (int row = mid + 1; row <= bottom; ++row) {
                curSum += matrix[row][l];
                sumArr[row - top] = curSum;
            }
            // 固定左边界l，遍历右边界r
            for (int r = l + 1; r <= right; ++r) {
                // 更新上半部分和
                curSum = 0;
                for (int row = mid; row >= top; --row) {
                    curSum += matrix[row][r];
                    sumArr[row - top] += curSum;
                }
                // 更新下半部分和
                curSum = 0;
                for (int row = mid + 1; row <= bottom; ++row) {
                    curSum += matrix[row][r];
                    sumArr[row - top] += curSum;
                }
                // 计算当前左右边界下跨中线的最大和
                maxCross = max(maxCross, kadane1D(sumArr));
            }
        }
        return max(max(maxUp, maxDown), maxCross);
    } else {
        // 垂直拆分，左右两半
        mid = left + (right - left) / 2;
        int maxLeft = maxSumDivideConquer(matrix, top, bottom, left, mid);
        int maxRight = maxSumDivideConquer(matrix, top, bottom, mid+1, right);
        // 计算跨垂直中线的最大和
        maxCross = INT_MIN;
        // 遍历所有上下边界组合
        for (int t = top; t <= bottom; ++t) {
            vector<int> sumArr(right - left + 1, 0);
            int curSum = 0;
            // 从中线往左累加
            for (int col = mid; col >= left; --col) {
                curSum += matrix[t][col];
                sumArr[col - left] = curSum;
            }
            curSum = 0;
            // 从中线往右累加
            for (int col = mid + 1; col <= right; ++col) {
                curSum += matrix[t][col];
                sumArr[col - left] = curSum;
            }
            // 固定上边界t，遍历下边界b
            for (int b = t + 1; b <= bottom; ++b) {
                // 更新左半部分和
                curSum = 0;
                for (int col = mid; col >= left; --col) {
                    curSum += matrix[b][col];
                    sumArr[col - left] += curSum;
                }
                // 更新右半部分和
                curSum = 0;
                for (int col = mid + 1; col <= right; ++col) {
                    curSum += matrix[b][col];
                    sumArr[col - left] += curSum;
                }
                // 计算当前上下边界下跨中线的最大和
                maxCross = max(maxCross, kadane1D(sumArr));
            }
        }
        return max(max(maxLeft, maxRight), maxCross);
    }
}

// 对外调用入口
void maxSumDivideConquerEntry() {
    vector<vector<int>> matrix = genRandomMatrix();
    printMatrix(matrix);
    int n = matrix.size();
    if (n == 0) {
        cout << "MAX SUM: 0" << endl;
        return;
    }
    int maxSum = maxSumDivideConquer(matrix, 0, n-1, 0, matrix[0].size()-1);
    cout << "MAX SUM: " << maxSum << endl;
}

内容的提问来源于stack exchange，提问作者user3308219