題目連結：
題目大意：
第一列給定一正整數 n （n ≦ 10000000），代表有 n 顆各自寫著數字的石頭。接著一列給定 n 個正整數（皆 ≦ 1000000000），代表每顆石頭上的數字。
現在有兩人，每人在自己的回合可以拿任意數量的石頭，而該回合得分為拿取的石頭裡的最小值。試問，在兩個人都採取最佳策略下，先手的總得分最多可以贏後手幾分？
範例輸入：
3
3 1 1
範例輸出：
2
解題思維：
先依據石頭上的數字大小由小到大排序。並命名為 S1 、 S2 、 …… 、 Sn。因為已排序過了，所以這些數字滿足 S1 ≦ S2 ≦ …… ≦ Sn （等等會用到這個性質）。
而現在這個問題可以使用動態規劃（Dynamic Programming，DP）解出。我們定義 Di 為 S1 、 S2 、 …… 、 Si 這個局面，其先手與後手的「最大」分數差值。並特別定義一數 D0 ＝ 0 （沒有任何石頭可拿，雙方差距 0 分）。
現在來看 Di 與 Di-1 的關係，可以看到
Di ＝ max(Di-1, Si - Di-1)
為什麼呢？我們分別討論 max 的逗號「,」左右兩邊的情況。
Di-1 代表的是：將 Di-1 的先手第一步所拿的石頭多加上現在這個石頭，也就是 Si 。因為 S1 ≦ S2 ≦ …… ≦ Si ，所以加入現在的 Si 並不會影響先手第一回合的得分（因為得分是看拿的石頭之最小值）。
Si - Di-1 代表：令先手第一回合只拿先在這顆石頭 Si 作為第一回合的得分，因此後手可以仿照 Di-1 的策略去得分，所以先手會與後手差 Si - Di-1 分。
兩種情況的最大值即是我們要求的 Di 。而 Dn 即是題目的所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
