软件工程概论-合作作业03-二维数组求最大联通子数组和
发布日期:2021-08-17 06:32:59 浏览次数:7 分类:技术文章

本文共 582 字,大约阅读时间需要 1 分钟。

  

  题目:返回一个二维整数数组中最大联通子数组的和。

  要求:输入一个二维整形数组,数组里有正数也有负数。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

  程序要使用的数组放在一个叫 input.txt 的文件中, 文件格式是:

  数组的行数,
  数组的列数,
  每一行的元素, (用逗号分开)
  每一个数字都是有符号32位整数,当然,行数和列数都是正整数。
程序设计思路:此次试验考虑到需要求最大联通子数组和。可以定义一个类(其中有value,x,y,neighbor,select),主函数里定义一个二维的对象,具体操作如下:

a:在二维对象中,先选出所有的正数,将其select值赋为1。

b:将孤立的数的select值赋为0,及将那些影响子数组连通性的数排除在外。

c:判断哪些正数的neighboe值为1,如果二维对象中所有的neighbor的值得个数大于3,则选出那个除了边缘点的点,记下他的坐标值。

d:对于上一步的那个“另类数”,选出他的一个“邻居”,使得这个子数组是联通的。这时选出的子数组中的对象的select值为1.

e:最后算出所有对象中select值为1的value的和。这个值就是二维最大联通子数组的和。

转载于:https://www.cnblogs.com/yifengyifeng/p/6679829.html

转载地址:https://blog.csdn.net/weixin_30838921/article/details/98953751 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Python中的可迭代对象,迭代器与生成器
下一篇:Linux学习笔记(三)Linux常用命令:链接命令和文件查找命令

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月10日 04时32分02秒