子矩阵的最大累加和问题

[编程题]子矩阵的最大累加和问题

热度指数：2476 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个矩阵matrix，其中的值有正、有负、有0，返回子矩阵的最大累加和

例如，矩阵matrix为：

-90 48 78

64 -40 64

-81 - 7 66

其中，最大的累加和的子矩阵为：

48 78

-40 64

-7 66

所以返回累加和209。

例如，matrix为：

-1 -1 -1

-1 2 2

-1 -1 -1

其中，最大累加和的子矩阵为：

2 2

所以返回4

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行有两个整数N，M。分别表示矩阵的行数/列数
接下来N行，每行M个整数表示矩阵内的数

输出描述:

输出一个整数表示答案

示例1

输入

输出

示例2

输入

3 3
-1 -1 -1
-1 2 2
-1 -1 -1

输出

备注:

算法知识视频讲解

查看答案及解析

helloxuanbao

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

#define max(a,b) ((a) > (b) ? (a) : (b))

int main(void) {
    int n, m, **matrix;
    scanf("%d%d", &n, &m);
    matrix = (int **) malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        matrix[i] = (int *) malloc(m * sizeof(int));
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    
    int *help, pre, maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        help = (int *) calloc(m, sizeof(int));
        for (int j = i; j < n; j++) {
            pre = 0;
            for (int k = 0; k < m; k++) {
                help[k] += matrix[j][k];
                pre = help[k] + pre;
                maxSum = max(maxSum, pre);
                pre = pre < 0 ? 0 : pre;
            }
        }
    }
    printf("%d\n", maxSum);
    return 0;
}

发表于 2022-04-04 21:30:27 回复(0)