整数数组重排：最小化前缀和交替加减表达式的值

给定数组[3,4,6,1,1]，我们需要重排数组，使得按规则S₁ - S₂ + S₃ - S₄ + S₅（其中Sᵢ是前i个元素的前缀和）计算的结果最小。原数组计算结果为10，以下是最优解法：

第一步：化简表达式 #

先把交替加减的表达式展开，拆解它和数组元素的对应关系：
对于长度为5的重排数组[a₁,a₂,a₃,a₄,a₅]，前缀和分别是：

• S₁ = a₁
• S₂ = a₁+a₂
• S₃ = a₁+a₂+a₃
• S₄ = a₁+a₂+a₃+a₄
• S₅ = a₁+a₂+a₃+a₄+a₅

代入表达式并展开：

E = S₁ - S₂ + S₃ - S₄ + S₅
  = a₁ - (a₁+a₂) + (a₁+a₂+a₃) - (a₁+a₂+a₃+a₄) + (a₁+a₂+a₃+a₄+a₅)

合并同类项后可以发现：

• 偶数位置的元素（a₂、a₄）系数全部抵消为0
• 奇数位置的元素（a₁、a₃、a₅）系数均为1

最终化简结果：E = a₁ + a₃ + a₅

第二步：确定最优重排策略 #

既然E等于重排后数组奇数位置元素的总和，要让E最小，只需要把数组中最小的⌈n/2⌉个元素放在奇数位置（n为数组长度，这里n=5，⌈5/2⌉=3），剩下的元素放在偶数位置即可。

对于示例数组[3,4,6,1,1]，最小的3个元素是1,1,3，剩下的两个元素是4,6。

第三步：验证最优解 #

随便一种符合策略的重排方式，比如[1,6,1,4,3]：

• 前缀和数组：[1,7,8,12,15]
• 计算表达式：1 - 7 + 8 - 12 + 15 = 5，比原数组的10小很多。

另一种重排方式[1,4,1,6,3]：

• 前缀和数组：[1,5,6,12,15]
• 表达式结果：1 -5 +6 -12 +15 =5，同样达到最小结果。

通用结论 #

• 当数组长度n为奇数时，交替加减前缀和的表达式等价于重排后奇数位置元素的总和，要最小化结果，就把最小的⌈n/2⌉个元素放在奇数位置。
• 当数组长度n为偶数时，类似推导可得表达式等价于- (a₂ + a₄ + ... + aₙ)，要最小化结果，需把最大的n/2个元素放在偶数位置（这样负的总和最小）。

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