如何优化Python代码以处理10^5规模的数组计算？

原代码的核心问题是每次循环都重新计算sum(d[i:])，这会导致时间复杂度达到O(n²)——对于长度10^{5的数组，需要执行约10}10次操作，自然耗时极长。

优化思路：维护后缀和，避免重复计算 #

sum(d[i:])表示从第i个元素到数组末尾的和，我们可以通过从前往后迭代维护当前后缀和的方式，把每次求和的操作从O(n)降到O(1)，整体时间复杂度变为O(n)，完全可以处理10^5规模的数组。

优化后的代码 #

d = [0, 1, 2, 5, ..., 0, 0]  # 最大长度10^5
max_sum = -float('inf')
max_idx = 0

# 初始后缀和为整个数组的和，对应i=0的情况
current_suffix_sum = sum(d)

for i in range(len(d)):
    current_calc = current_suffix_sum * (i + 1)
    if current_calc > max_sum:
        max_sum = current_calc
        max_idx = i + 1
    # 更新后缀和：去掉当前元素d[i]，得到下一轮的后缀和
    if i < len(d) - 1:
        current_suffix_sum -= d[i]

优化原理 #

1. 先计算一次数组的总和作为初始后缀和（O(n)时间）
2. 每轮循环中，直接用当前维护的后缀和计算目标值，然后通过**减去当前元素d[i]**得到下一轮的后缀和（O(1)时间/轮）
3. 整个循环仅执行n次，总时间复杂度为O(n)，处理10^5数组仅需数万次操作，效率提升几个数量级。

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