软件工程第三次作业--最大子段求和

佚名 5年前 (2019-04-15) 随笔 943人围观抢沙发百度已收录

一、题目要求

题目(1)：最大连续子数组和（最大子段和）
问题：给定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。
--引用自《百度百科》

二、解题思路

若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且i<=j<=n。则所求的最大子段和为max b[j]，1<=j<=n。由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的递推方程为:b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

三、源代码

coding.net代码链接
源代码

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：albert time:2019/4/15
def getNum():
    nums =[]
    iNumStr=input("请输入数字(回车结束):")
    while iNumStr !="":
        nums.append(eval(iNumStr))
        iNumStr=input("请输入数字（回车结束）：")
    return nums
def maxnumbers(numbers):
    b=[]
    b=numbers.copy()
    for i in range(1,len(numbers)):
        if b[i-1]>0:
            b[i]=b[i-1]+numbers[i]
        else:
            b[i]=numbers[i]
    return max(b)
n=getNum()
if len(n)==0:
    print("列表为空")
else:
    m=maxnumbers(n)
    if m<0:
        m=0
    print("最大子段和是：{}".format(m))

四、条件/组合覆盖

流程图

测试代码

import unittest
import maxarray

num1=[-1,-2,-3]
num2=[10,0]
num3=[1,-2,10,4,-5]
num4=[-1,12,-3,4,-5]
class MyTestCase(unittest.TestCase):
    def test_maxnumbers1(self):
        array1=maxarray.maxnumbers(num1)
        self.assertEqual(-1, array1, 'ERROR!')

    def test_maxnumbers2(self):
        array2= maxarray.maxnumbers(num2)
        self.assertEqual(10, array2, 'ERROR')

    def test_maxnumbers3(self):
        array3 = maxarray.maxnumbers(num3)
        self.assertEqual(14, array3, 'ERROR')

    def test_maxnumbers4(self):
        array4 = maxarray.maxnumbers(num4)
        self.assertEqual(13, array4, 'ERROR')

if __name__ == '__main__':
    unittest.main()