多维数组和矩阵----子矩阵最大累加和
2023-03-14 09:45:28 时间
题目:给定一个矩阵matrix,其中的值有正、有负、有0,返回子矩阵的最大累加和。
例如,matrix为: -1 -1 -1 -1 2 2 -1 -1 -1 其中最大累加的子矩阵为:2 2,所以返回 4
思路:
解法一:暴力破解,查找出所有的子矩阵,时间复杂度太高了,不可取。
解法二:假定只有一行,那就跟求最大和子数组一样。
如果限定两行,可以把两行按列求和,
同上所有我们从把第一行当做起点,依次累加后面的每一行后,都求一个最大子数组和
以第二行作为起点,依次累加后面的每一行后,都求一个最大子数组和 每次求出来的和与历史最大值比较,如果更大,则更新 。
Arrays.fill(arr, 0);//快速地将arr的每个元素都设定为0
代码:
import java.util.Arrays; public class MaxSubMatrix { static int maxSum(int [][]matrix){ int beginRow = 0;// 以它为起始行 final int M = matrix.length; final int N = matrix[0].length; int []sums = new int[N]; // 按列求和 int max = 0; // 历史最大的子矩阵和 while(beginRow<M){ for (int i = beginRow; i < M; i++) { // 按列累加 for (int j = 0; j < N; j++) { sums[j] += matrix[i][j]; } // 累加完成,调用上一篇博客求最大子数组累加和的方法 int t = MaxSubArray.findByDp(sums); if (t>max) { max = t; } } // sums 清零 Arrays.fill(sums, 0); // 快速地将sums的每个元素都设定为0 beginRow++; } return max; } public static void main(String[] args) { int[][] matrix = { {-90, 48, 78}, {64, -40, 64}, {-81, -7, 66} }; matrix = new int[][]{{1, 2, -1}}; int res = maxSum(matrix); System.out.println(res); } }
结果:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的