假設 $n$ 是偶數。如果我們忽略刪除相鄰數的條件，即可以任選兩個數相減，那么答案應該是前 $\frac{n}{2}$ 大的數（記作“較大數”）的和減去前 $\frac{n}{2}$ 小的數（記作“較小數”）的和。

容易發現，當我們只能選相鄰的數相減時，依然可以達到這個答案，因為在任意時刻，總存在至少一對較大數與較小數相鄰。

當 $n$ 是奇數，那么一定有一個元素不被選，且這個元素一定在奇數位，這樣才能把數組分成長度為偶數的兩段。枚舉不被選的位置，用對頂堆維護前后兩段的答案即可。

時間復雜度 $O(n\log n)$。

提交記錄