maxsubarray函数时间复杂度计算及优化至O(n²)及以下的咨询

原代码时间复杂度分析 #

我们直接拆解代码的执行开销：

• 外层循环总共有 n-1 次迭代（n 是输入列表的长度），属于*O(n)*量级的基础遍历
• 每次迭代中最多会触发3次sum()调用：分别是判断minlist的和、比较minlist和globallist的和，sum()的时间复杂度和传入列表的长度成正比
  最坏场景下（比如输入全为正整数的数组），minlist和globallist的长度会从1逐步增长到n，所有sum()调用的总开销为 1+2+3+...+n = n(n+1)/2，整体时间复杂度为O(n²)，本身没有超过n²的量级，但存在很大的优化空间。

优化方案 #

核心优化思路 #

原代码的性能瓶颈全部来自重复的sum()遍历求和操作，我们只需要新增两个变量维护当前子数组的和、全局最大子数组的和，就能把求和操作从O(k)降到O(1)。如果需要进一步避免列表拷贝的开销，还可以通过存储子数组起止索引替代直接存储子数组内容，最终可以把整体时间复杂度降到O(n)，远优于O(n²)的要求。

优化后代码（保留返回子数组的能力） #

def maxsubarray(inputlst):
    # 处理空输入边界，避免原代码的索引报错问题
    if not inputlst:
        return []
    size = len(inputlst)
    minlist = [inputlst[0]]
    current_sum = inputlst[0] # 维护当前minlist的和，避免重复sum计算
    globallist = [inputlst[0]]
    global_sum = inputlst[0] # 维护全局最大子数组的和，避免重复sum计算
    
    for i in range(1, size):
        # 替换insert为append，等价操作但性能更高
        minlist.append(inputlst[i])
        current_sum += inputlst[i]
        
        if current_sum > inputlst[i]:
            if current_sum > global_sum:
                globallist = list(minlist)
                global_sum = current_sum
        elif current_sum < inputlst[i]:
            minlist = [inputlst[i]]
            current_sum = inputlst[i]
            if current_sum > global_sum:
                globallist = list(minlist)
                global_sum = current_sum
    return globallist

极致优化方案（仅需返回最大和时） #

如果业务不需要返回具体的子数组元素，只需要返回最大子数组的和，可以完全去掉列表存储和拷贝操作，严格实现O(n)时间复杂度、O(1)空间复杂度：

def maxsubarray_sum(inputlst):
    if not inputlst:
        return 0
    current_sum = global_sum = inputlst[0]
    for num in inputlst[1:]:
        current_sum = max(num, current_sum + num)
        global_sum = max(global_sum, current_sum)
    return global_sum

内容的提问来源于stack exchange，提问作者zayant21