Codility最大利润问题：累加差和为何等价于双索引差值解法？

核心数学原理：望远镜求和 #

假设我们在第k天买入，第m天卖出（m > k），把这期间每天的股价差累加起来：

(A[k+1] - A[k]) + (A[k+2] - A[k+1]) + (A[k+3] - A[k+2]) + ... + (A[m] - A[m-1])

展开后你会发现，中间的所有项都会相互抵消：A[k+1]和-(A[k+1])抵消，A[k+2]和-(A[k+2])抵消……最后只剩下A[m] - A[k]，这正好是直接计算买卖日的价格差。

结合代码逻辑理解 #

这段代码本质是用Kadane算法找每日差价数组的最大子数组和，而这个最大子数组和对应的就是一次买卖的最大利润：

• acc变量用来跟踪从某个潜在买入点开始到当前天的累计盈利（也就是差价总和）
• 当acc变为负数时，说明从之前的买入点到当前天已经亏损，此时重置acc为0，相当于放弃之前的买入点，重新寻找新的更低的买入点
• 过程中不断更新max，记录所有累计盈利中的最大值，也就是我们要找的最大利润

比如你提到的示例：A[5]-A[1]的利润，对应累加的是第1天到第5天的每日差价，中间项抵消后结果完全等于直接计算的差价，所以两种方式得到的结果一致。

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