最大子矩阵和动态规划c++代码

以下是最大子矩阵和的动态规划代码实现：

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

int maxSubArraySum(int* arr, int n) {
    int max_so_far = arr[0];
    int max_ending_here = arr[0];
    for (int i = 1; i < n; i++) {
        max_ending_here = max_ending_here + arr[i] > arr[i] ? max_ending_here + arr[i] : arr[i];
        max_so_far = max_so_far > max_ending_here ? max_so_far : max_ending_here;
    }
    return max_so_far;
}

int maxSubmatrixSum(int** matrix, int n, int m) {
    int max_sum = -2147483647;
    int* tmp = (int*) malloc(sizeof(int) * n);

    for (int left = 0; left < m; left++) {
        for (int i = 0; i < n; i++) {
            tmp[i] = 0;
        }

        for (int right = left; right < m; right++) {
            for (int i = 0; i < n; i++) {
                tmp[i] += matrix[i][right];
            }

            int curr_max = maxSubArraySum(tmp, n);
            max_sum = max_sum > curr_max ? max_sum : curr_max;
        }
    }

    free(tmp);
    return max_sum;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    int** matrix = (int**) malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++) {
        matrix[i] = (int*) malloc(sizeof(int) * m);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    int ans = maxSubmatrixSum(matrix, n, m);
    printf("%d\n", ans);

    for (int i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);

    return 0;
}

该代码使用了两层循环，分别遍历左右边界，并在内部再用一层循环计算每一行的前缀和，然后通过 `maxSubArraySum` 函数计算每个子矩阵的最大子数组和，最后取其中的最大值即为最终答案。