首页 > 试题广场 >

子矩阵的最大累加和问题

[编程题]子矩阵的最大累加和问题
  • 热度指数：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

输入

3 3
-90 48 78
64 -40 64
-81 -7 66

输出

209
示例2

输入

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

输出

4

备注:

算法知识视频讲解
添加回答
Go
喜欢编程滑雪乒乓球篮球头像 喜欢编程滑雪乒乓球篮球
这道题标简单就离谱
发表于 2021-11-10 09:04:27 回复(0)
提交观点

问题信息

动态规划
上传者：小小
难度：
1条回答 4333浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号