软件工程（2019）第三次作业

佚名 6年前 (2019-04-17) 随笔 836人围观抢沙发百度已收录

最大连续子数组和

ProjectAddress

问题

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

分析

这是一道动态规划的题目，解决动态规划问题可以采用分治法和递归方法。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

项目目录结构

SEProject3(工程名)
- TestDemo（测试包）
  - report
    - report.log（用于保存测试用例调用的日志文件）
  - test_case（放置一些测试用例）
    - test_sumOfMaximumSubsection.py（关于字符串测试的样例）
  - runtest.py（通过测试套件TestSuite来组装多个测试用例）
- sumOfMaximumSubsection.py（测试代码）

解决方案

源代码（sumOfMaximumSubsection.py）：

 def returnSumOfMaximumSubsection(arrayList:list)->int:
     """
     :param arrayList: 传入数列,参数类型为列表
     :return:最大子数组之和
     """
     sum = tempSum = 0
     for i in range(len(arrayList)):
         if tempSum + arrayList[i] > sum:
             tempSum += arrayList[i]
             sum = tempSum
         else:
             tempSum = arrayList[i] if arrayList[i] > 0 else 0
     return sum

构造测试用例（runtest.py）：
这里的测试用例分为两个部分，具有条件组合覆盖的test_1和非法输入测试test_2
定义了MAXIMUM为界定范围，其值为65536。超过范围的数字将返回0。

 import time
 import unittest
 from functools import wraps
 from SEProject3.sumOfMaximumSubsection import returnSumOfMaximumSubsection as testPy
 def logit(logfile='E:/Programmer/PYTHON/SEProject3/TestDemo/report/report.log',
             doc=''):
     def logging_decorate(func): 
      @wraps(func)           
         def wrapped_function(*args, **kwargs): 
             log_string = time.strftime('%Y_%m_%d_%H_%M_%S ', time.localtime(time.time())) + func.__name__ + ' was called.\n' + doc + '\n'

             with open(logfile, 'a') as opened_file:
             opened_file.write(log_string)
             return func(*args, **kwargs)
         return wrapped_function
     return logging_decorate
 MAXIMUM = 65536 # 设定上下界阈值
 class TestResultsMethods(unittest.TestCase):

     def setUp(self):
         pass

     def tearDown(self):
         pass

     @logit()
     def test_1(self):
         """
         测试正常数据
         :return:
         """
         tempList = [0, 0, 0, 0]
         self.assertEqual(testPy(tempList), 0, msg=str(tempList)+' Wrong!')
         tempList = [-1, -1, -1]
         self.assertEqual(testPy(tempList), 0,msg=str(tempList)+' Wrong!')
         tempList = [1, 2, 3, 4]
         self.assertEqual(testPy(tempList), 10, msg=str(tempList) + ' Wrong!')
         tempList = [1, 2, 3, -4, 5, 6]
         self.assertEqual(testPy(tempList), 11, msg=str(tempList) + ' Wrong!')

     @unittest.skip('暂时跳过用例test_2的测试')
     def test_2(self):
        """
        测试非法数据
        定义MAXIMUM为非法数据，返回0
        :return:
        """
        tempList = [MAXIMUM, MAXIMUM]
        self.assertEqual(testPy(tempList), 0, msg=str(tempList) + ' Wrong!')
        tempList = [MAXIMUM, -MAXIMUM]
        self.assertEqual(testPy(tempList), 0, msg=str(tempList) + ' Wrong!')
     if __name__ == '__main__':
         unittest.main()

构造测试集（runtest.py）：

  import unittest
  from SEProject3.TestDemo.test_case import test_sumOfMaximumSubsection as test
  suite = unittest.TestSuite()
  suite.addTest(test.TestResultsMethods("test_1"))
  suite.addTest(test.TestResultsMethods("test_2"))
  if __name__ == "__main__":
      runner = unittest.TextTestRunner()
      runner.run(suite)

测试结果

Ctrl+Shift+F10，运行runtest.py

结果表明，通过了一个测试，失败了一个测试。将sumOfMaximumSubsection.py做出如下修改：

 MAX = 65536
 def returnSumOfMaximumSubsection(arrayList:list)->int:
 """
 :param arrayList: 传入数列,参数类型为列表
 :return:最大子数组之和
 """
 sum = tempSum = 0
 for i in range(len(arrayList)):
     if abs(arrayList[i]) < MAX:
         if tempSum + arrayList[i] > sum:
             tempSum += arrayList[i]
             sum = tempSum
         else:
             tempSum = arrayList[i] if arrayList[i] > 0 else 0
 return sum

运行结果如图所示：

结果表明，样例通过。
我们再来看看日志文件中的内容：