求时间复杂度为O(n³)的最大子数组和算法及实现

当然存在时间复杂度为O(n³)的最大子数组和算法！它是最直观的暴力解法，思路比你已经实现的解法还要简单——就是枚举所有可能的子数组起点、终点，再通过第三层循环逐个累加计算子数组的和，全程用三层嵌套循环完成。

先澄清一个小细节 #

你写的那段标注为O(n²)的代码，其实实际时间复杂度也是O(n³)哦！因为每次调用sum(A[i:j+1])时，Python的sum函数会遍历从i到j的所有元素，这一步的时间复杂度是O(j-i+1)，嵌套在两层循环里，总时间就变成了O(n³)。真正的O(n²)解法需要借助前缀和数组，提前计算好前缀和后，用O(1)时间就能得到任意子数组的和。

直白的O(n³)算法实现 #

下面是完全基于三层嵌套循环的O(n³)解法，逻辑非常清晰：

def mssl_cubic(arr):
    n = len(arr)
    max_sum = float('-inf')  # 初始设为负无穷，兼容全负数的输入情况
    start = 0
    end = 0

    # 第一层循环：枚举子数组的起始索引i
    for i in range(n):
        # 第二层循环：枚举子数组的结束索引j（j >= i）
        for j in range(i, n):
            current_sum = 0
            # 第三层循环：从i到j逐个累加元素，计算当前子数组的和
            for k in range(i, j + 1):
                current_sum += arr[k]
            # 更新最大和及对应的起止索引
            if current_sum > max_sum:
                max_sum = current_sum
                start = i
                end = j
    return max_sum, start, end

if __name__ == '__main__':
    A = [18, -10, 30, 23, -26]
    ans = mssl_cubic(A)
    print(ans)  # 输出 (51, 0, 3)，对应子数组[18, -10, 30, 23]

复杂度说明 #

三层循环每层最多执行n次，总操作次数是$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1} (j-i+1)$，最终时间复杂度为O(n³)。

不过要注意，这个算法的效率极低，只适合用来理解最大子数组和问题的最基础逻辑，实际开发中肯定会优先选择你实现的O(n)时间复杂度的Kadane算法，它是这个问题的最优解。

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