数组两最大不重叠正差值求和算法正确性验证及等价问题说明

你对辅助函数的功能存在误解，max2DiffForward和max2DiffBackward返回的就是对应区间的全局最大单次差值，完全符合你最初的设计思路。

原理说明 #

1. max2DiffForward的功能正确性
   max2DiffForward(arr)返回的数组forward中，forward[i]的定义是「数组前i+1个元素（即arr[0]到arr[i]区间内）可获得的单次交易最大利润」，这本身就是左侧区间的全局最大差值：

• 遍历过程中维护到当前位置为止的最低买点mi，以及当前区间的最高卖点ma
• 遇到比mi更低的价格时，重置买点和卖点（因为新的买点出现后，后续的卖点要基于这个更低的买点计算才能得到更大差值）
• 遇到比ma更高的价格时，更新卖点并重新计算最大差值
  这个逻辑是求前缀区间单次交易最大利润的标准实现，结果是全局最优的。

2. max2DiffBackward的功能正确性
   该函数先将数组翻转，用和前向遍历完全对称的逻辑求翻转数组的前缀最大利润，再把结果翻转回来，最终得到的backward[i]就是「数组从i到末尾（即arr[i]到arr[-1]区间内）可获得的单次交易最大利润」，也就是右侧区间的全局最大差值，逻辑同样正确。
3. best2Diff的逻辑正确性

• 初始值取backward[0]，对应整个数组只做一次交易的最大利润
• 遍历所有分割点i：前半段0~i的最大利润是forward[i]，后半段i+1~末尾的最大利润是backward[i+1]，两者之和就是两次交易分割在i处的最大利润，逐次更新最大值即可
• 末尾的else分支取forward[i+1]（也就是forward[-1]，同样是整个数组单次交易的最大利润）属于冗余逻辑，但不影响最终结果

验证用例 #

你担心的逻辑漏洞不存在，我们可以用LeetCode第123题的标准测试用例验证：

输入数组[3,2,6,5,0,3]，预期输出7（2买6卖赚4，0买3卖赚3，总和7）

• 前向遍历结果forward = [0,0,4,4,4,4]
• 后向遍历结果backward = [4,4,3,3,3,0]
• 遍历分割点时，i=2和i=3时都能得到4+3=7的最大值，结果符合预期。

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