编程思维任务之(28) 连续元素的最大总和

给定一个数组，计算该数组内所有可能的连续元素的最大总和。这些数字将是正值和负值的混合。

如果序列中的所有数字都是非负数，答案将是整个数组的总和。如果数组中的所有数字都是负数，你的算法应该返回0。同样地，一个空的数组应该导致你的算法返回0

largestSum([-1,-2,-3]) == 0

biggestSum([]) == 0

largestSum([1,2,3]) == 6

很简单，对吗？

如果混合使用正数和负数，这就变得更有趣了。

*largestSum([31,-41,59,26,-53,58,97,-93,-23,84]) == 187 *

最大的和来自于位置3到7的元素：

59+26+(-53)+58+97 == 187

一旦你的算法能够解决这些问题，测试案例将以越来越大的随机问题规模来尝试你的提交。

简洁有惊喜的写法

def largest_sum(arr):
    sumsub = max_sum = 0
    for n in arr:
        sumsub = max(sumsub + n, 0)
        max_sum = max(sumsub, max_sum)
    return max_sum

下面的写法技稍逊一筹

但优点是，既可以返回最大值，也可以选择最大值对应的序列。但需要对下面代码做修改！作为家庭作业完成

def largest_sum(arr):
    if not arr:return 0
    lft,total = 0,0
    s,sub = 0,[]
    minum,maxs = 0,0
    for n in arr:
        lft += n
        if n >= 0:
            s += n
        elif n < 0:
            maxs = s
            s = 0

        if lft < minum:
            sub.append(s-n)
            minum = lft
        else:
            if lft - minum > total:
                total = lft - minum
    return max(total,maxs)

课堂上深入讨论！

这道题有同学想到的几种算法都超时了！需要了解几种提高时间效率的思路

包括：

数学发现减少无谓的计算例如素数判断 int(math.sqrt(n))+1

记忆法避免重复的计算，详细如链接👇