首页 > 试题广场 >

最大子矩阵

[编程题]最大子矩阵

热度指数：17246 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。

输入描述:

输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。
再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。
已知矩阵中整数的范围都在[-127, 127]。

输出描述:

输出最大子矩阵的大小。

示例1

输入

输出

算法知识视频讲解

hayabusap

发表于 2020-05-11 15:22:34

题目描述已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。输展开全文

domeya

发表于 2021-07-13 21:56:41

思路先写两重循环枚举起点行k1到终点行k2，再写一个循环遍历每列i，将列i压缩成一个数字，它表示第i列k1~k2行的前缀和（用二维前缀和预处理），那么就变成了一个1*n的矩阵，即一个一维数组，然后求其最大子段和，同时取max即可。时间复杂度O(n^3)。 AC代码 #include <bi 展开全文

烤肉__

发表于 2023-03-31 12:59:21

如果说，这题用一个预处理一个二维前缀和，然后枚举子矩阵的左上角与右上角，那么我们可以用O(n4)O(n^4)O(n4)的时间复杂度得到答案。不过对于这题n=100来说，1004=108100^4=10^81004=108会超时。所以我们要想办法优化，最蛋疼的点其实在于暴力的枚举会涉及非常多无用的状展开全文

静寂旮旯

发表于 2022-04-11 21:01:14

关于暴力的解题思路没什么可说的，无非是搜索模式的不同。此题应该属于线性dp的一种变化，对于一位数组的连续子数组最大和的状态表达式是dp[i]=max(dp[i−1]+v[i],v[i])dp[i] = max(dp[i-1]+v[i],v[i])dp[i]=max(dp[i−1]+v[i],v[ 展开全文

牛客687146177号

发表于 2022-04-28 14:47:56

动态规划：利用题题目DP5（连续自数字最大和）的思路，首先将矩阵分为第一列，第二列... 用字母表示：m0,m1,m2...m(n-1)，得到n个数组，然后：先求第一个数组的最大子数组值a1。求第一个数组+第二个数组得到的数组的最大子数组值a2。 m0+m1+m2的最大子数组值a3 m0+. 展开全文