数组中最大子数组2

时间：2021-04-01 18:41:17 阅读：39 评论：0 收藏：0 [点我收藏+]

一.实验目的

1，一维数组变为二维数组

2，二维数组的数据从文本中读取，文本的内容符合指定规格

3，给出单元测试的测试结果以及代码覆盖率的结果,撰写博客。

二.实验内容

# 求得二维数组array1中所能组成的所有一维数组放入到brray中 
# 再利用求一维数组中最大子数组的和 求得每个一维数组即brray每一列最大子数组（展开后即为array1子矩阵）的和
# 在所有和中最大的即为二维数组array1中最大子矩阵的和
def MaxNums(array,leng):
	maxSumOfArry=maxSum=array[0]
	# 当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。
	# 如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。
	for i in range(1,leng):
		maxSumOfArry=max(maxSumOfArry+array[i],array[i])
		maxSum=max(maxSum,maxSumOfArry)
	return maxSum
def Maxmarry(array1):
	brray=[[0 for i in range (100)]for j in range(100)]
	a=0
	for i in range(1,hig+1):
		a=a+i
	for i in range(0,a):
		for j in range(0,leng):
			brray[i][j]=0
	# 计算二维数组Array所能组成的所有一维数组 依次放入到Brray中
	h=0
	for n in range(0,hig):
		for i in range(0,hig-n):
			for j in range(0,leng):
				for k in range(0,n+1):
					brray[h][j]+=array1[i+k][j]
			h=h+1
	Max=MaxNums(brray[0],leng)
	for i in range(1,a):
		Max=max(Max,MaxNums(brray[i],leng))
	return Max

with open(r‘C:\Users\tbd\Desktop\新建文本文档.txt‘) as file_obj:
	content = file_obj.read()
xlist=content.split(",\n")
lis=xlist[2].split("\n")
for i in range(int(xlist[0])):
	lis[i]=lis[i].split(",")
hig=int(xlist[0])
leng=int(xlist[1])
for i in range(hig):
	for j in range(leng):
		lis[i][j]=int(lis[i][j])
print(Maxmarry(lis))

输入的二维数组，txt文件如下：

技术分享图片

输出结果：

技术分享图片

很明显的最大子数组由第三列和第四列组成，结果是28

三.单元测试

代码如下：

import unittest
from unittest import TestCase 
from MaxMarrry import *
class Testppp(unittest.TestCase):
	def test_1(self):
		lis = [[5,6,-3,8,-9,2],[1,-12,20,0,-3,-5],[-9,-7,-3,6,7,-1]]
		self.assertNotEqual(Maxmarry(lis),20)
	def test_2(self):
		lis = [[8,-10,-3,26,-11,-1,-6,12,17,6,28,4],[20,-13,-20,-13,-15,-254,5,8,9,-4,-9,29],
			   [-11,18,-25,9,12,-9,-2,23,8,-1,3,-14],[-16,-7,0,201,-1,309,3,6,-18,11,24,-8],
			   [-1,-7,11,100,21,292,-2,2,-18,-8,-10,9],[26,-11,-19,-18,20,-981,2,-14,12,-14,1,27],
			   [9,-20,5,28,-15,26,-20,-8,-16,30,3,20],[-6,-7,-5,-9,-16,-15,5,-16,22,-17,11,-18]]
		self.assertEqual(Maxmarry(lis),964)
if __name__ == ‘__main__‘:
	unittest.main()

　　测试结果：

技术分享图片