代码地址

题目

最大连续子数组和（最大子段和）

给定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。

-- 引用自《百度百科》

思路

从数组一个值开始累加，并记录下最大值，当前和。如果当前和小于0则置0，因为加上一个小于0肯定变小，当前和不小于等于0的话，所有数加上当前和都会变大。

流程图

有些人表面风光，背地里for循环怎么写都要百度

代码实现（Py）

func = lambda x: x>0 and x or 0

def MaxSubArray(array):

    maxSum = 0

    thisSum = 0

    for i in range(len(array)):

        thisSum = func(thisSum+array[i])

        maxSum = max(thisSum,maxSum)

    return maxSum

测试

覆盖标准

采用条件组合覆盖

测试用例分析

len(array)<0 AH 符合条件为[]

len(array)>0 AB...BH

CDFI array[i]为负数 thisSum为正加一个大于thisSum绝对值的负数例如[1,2,-1]

CDFGI array[i]为正数 thisSum为任意值加一个正数之后小于max 例如[1,2,3]

CEFI array[i]为负数 thisSum为任意值加一个比thisSum的相反数小的数例如[-1,-2,-3]

CEFGI 永不成立

符合上述条件可总结为一个数组[7,-4,-6]

[7,]满足CDFGI

[7,-4]满足CDFI

[7,-4,-6]满足CEFI

流程图

有些人表面风光，背地里for循环怎么写都要百度

代码实现

import unittest

from  MaxSubarray import MaxSubArray

class TestMaxSubArrayFunc(unittest.TestCase):

    def test_Empty(self):

        self.assertEqual(0,MaxSubArray([]))

    def test_AB_BH(self):

        self.assertEqual(7,MaxSubArray([7,-4,-6]))

if __name__ == '__main__':

        unittest.main(verbosity=2)

测试结果

有些人表面风光，背地里for循环怎么写都要百度

总结

多加练习