数组中最大的子数组之和

时间：2021-03-14 00:10:07 阅读：30 评论：0 收藏：0 [点我收藏+]

一、程序分析

使用Python语言进行编译，读取一个文件，内容包括数组数和数组元素个，求数组中的最大子数组之和

 1 class MSA:
 2     #读取文件
 3     def read_file(self,file_path):
 4         with open(file_path, "r") as f:
 5             str = f.read()
 6         return str      #返回文件内容
 7 
 8 
 9     #读取数据预处理
10     def pretreatment(self,str):
11         strlist = str.split(":")  # 文件内容按“：”切割为两部分，第一部分为数组长度，第二部分为数组内容
12         numlist = strlist[1].split(",")  # 数组内容按“，”切割，获取每个元素
13         n = int(strlist[0])
14         lst = []
15         for i in range(len(numlist)):
16             lst.append(int(numlist[i]))
17         return lst,n    #返回数组内容列表，数组长度
18 
19 
20     #计算最大子数组及下标
21     def Calc(self,lst,n):
22         max = 0
23         for i in range(n):
24             for j in range(i, n):
25                 sum = 0
26                 for k in range(i, j+1):
27                     sum = sum + lst[k]
28                     if sum > max:
29                         max = sum
30                         begin = i
31                         end = j - 1
32         return max, begin, end      #返回计算结果
33 
34 if __name__=="__main__":
35     file_path="C:/Users/Sun Tianwen/Desktop/data.txt"   #文件路径
36     max=0
37     begin=0
38     end=0
39     msa=MSA()
40     str=msa.read_file(file_path)    #读取文件
41     lst,n=msa.pretreatment(str)   #文件内容预处理
42     max,begin,end=msa.Calc(lst,n)  #求最大子数组之和及下标
43 
44     print("最大子数组的和：",max)
45     print("开始下标:",begin)
46     print("结束下标:",end)

二、单元测试

使用pycharm中的unittest进行测试

单元测试代码

from unittest import TestCase
from max_array import MSA

class TestMSA(TestCase):

    def test_calc_1(self):
        self.MSA=MSA
        self.assertEqual(self.MSA.Calc(self,[-1, 20, -5, 30, -4],5),(45,1,2))

    def test_calc_2(self):
        self.MSA = MSA
        self.assertEqual(self.MSA.Calc(self, [-32, -10, 33, -23, 32, -12, 41, -12, 1, 3, 5, -98, 70, -21, 10, -9, 61], 17), (111, 12, 15))