如何优化二维数组中面积不超指定值的子矩形最大和求解代码？

你的原代码核心问题是多层嵌套循环+重复计算子矩阵和，时间复杂度高达O(R³C³)，对稍大的数组会严重卡顿。下面是几个针对性的优化技术，能大幅提升性能：

1. 前缀和数组：O(1)快速计算子矩阵和 #

先预处理一个前缀和数组，把任意子矩阵的求和操作从O(RC)降到O(1)，这是最核心的优化。
前缀和数组prefix的定义：prefix[i][j]表示从原数组左上角(0,0)到(i-1,j-1)的子矩阵所有元素的和。计算公式：

prefix[i][j] = field[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];

之后，任意子矩阵从(X,Y)到(x,y)的和可以通过以下公式直接算出：

sum = prefix[x+1][y+1] - prefix[X][y+1] - prefix[x+1][Y] + prefix[X][Y];

2. 提前过滤面积超标的子矩阵 #

原代码在求和过程中才检查面积是否超限，现在可以先计算当前子矩阵的面积(x-X+1)*(y-Y+1)，如果超过window_size，直接跳过这个分支的计算，避免无效的求和操作。

3. 缩小遍历范围，减少无效循环 #

对于每个起始点(X,Y)，当确定子矩阵的高度h = x - X + 1后，最大允许的宽度w = window_size / h，因此y的遍历上限可以设为Y + w - 1（不超过数组列数），不用遍历到数组末尾，直接减少内层循环次数。

4. 剪枝优化：提前终止循环 #

如果当前找到的最大和max_sum已经等于「单个最大元素 × window_size」（比如所有元素都是正数时，这就是理论最大值），可以直接终止所有循环，因为不可能找到更大的和了。

优化后的完整代码 #

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main() {
    int max_sum = INT_MIN;
    int loopCount = 0; // 性能统计用

    // 输入数据
    int field[4][5] = {
        {0, -5, 3, 4, 9},
        {10, 21, 18, -11, 0},
        {0, -2, 5, 9, 11},
        {12, 7, 8, 3, -1}};
    int fieldCol = 5;
    int fieldRow = 4;
    int window_size = 6;

    // 边界处理
    if (window_size <= 0) {
        printf("0");
        return 0;
    }
    int max_area = fieldCol * fieldRow;
    if (window_size > max_area) {
        window_size = max_area;
    }

    // 步骤1：预处理前缀和数组
    int **prefix = (int**)malloc((fieldRow + 1) * sizeof(int*));
    for (int i = 0; i <= fieldRow; i++) {
        prefix[i] = (int*)calloc(fieldCol + 1, sizeof(int));
    }
    for (int i = 1; i <= fieldRow; i++) {
        for (int j = 1; j <= fieldCol; j++) {
            prefix[i][j] = field[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }

    // 步骤2：提前找到数组中的最大元素，用于剪枝
    int max_val = INT_MIN;
    for (int i = 0; i < fieldRow; i++) {
        for (int j = 0; j < fieldCol; j++) {
            if (field[i][j] > max_val) {
                max_val = field[i][j];
            }
        }
    }
    int theoretical_max = max_val * window_size;

    // 遍历所有可能的子矩阵
    for (int X = 0; X < fieldRow; X++) { // 起始行
        for (int x = X; x < fieldRow; x++) { // 结束行
            int h = x - X + 1;
            int max_w = window_size / h;
            if (max_w == 0) break; // 高度已经超过window_size，直接跳过当前X的后续x
            for (int Y = 0; Y < fieldCol; Y++) { // 起始列
                // 计算列的最大遍历范围
                int y_max = (Y + max_w - 1) < fieldCol ? (Y + max_w - 1) : (fieldCol - 1);
                for (int y = Y; y <= y_max; y++) { // 结束列
                    loopCount++;
                    int area = h * (y - Y + 1);
                    if (area > window_size) continue;

                    // 用前缀和快速计算子矩阵和
                    int sum = prefix[x+1][y+1] - prefix[X][y+1] - prefix[x+1][Y] + prefix[X][Y];
                    if (sum > max_sum) {
                        max_sum = sum;
                        // 剪枝：如果已经达到理论最大值，直接退出所有循环
                        if (max_sum == theoretical_max) {
                            goto end_calculation;
                        }
                    }
                }
            }
        }
    }

end_calculation:
    printf("%d", max_sum);
    printf("\nloop count %d", loopCount);

    // 释放前缀和数组内存
    for (int i = 0; i <= fieldRow; i++) {
        free(prefix[i]);
    }
    free(prefix);

    return 0;
}

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