主題
題目連結：
題目意譯：
你有 k 個袋子。你被給定一個索引值從 0 開始數的整數陣列 weights，其中 weights[i] 為第 i 顆彈珠的重量。同時你也被給定一整數 k。
根據以下規則將彈珠分配到 k 個袋子中：
沒有袋子是空的、
如果第 i 顆和第 j 顆彈珠在同一袋中，則所有有著藉由 i 到 j 之間的索引值之彈珠也應在同一個袋子中、
如果某個袋子裝著索引值為 i（含）到 j（含）之間所有的彈珠，則該袋子的成本為 weights[i] + weights[j]。
經過彈珠分配之後的分數為 k 個袋子的成本之總和。
回傳在所有的彈珠分配方式中，最大分數與最小分數的差值。
限制：
1 ≦ k ≦ weights.length ≦ 10 ^ 5
1 ≦ weights[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： weights = [1,3,5,1], k = 2
輸出： 4
解釋：
分配法 [1],[3,5,1] 將會得到最小分數 (1 + 1) + (3 + 1) = 6。
分配法 [1,3],[5,1] 將會得到最大分數 (1 + 3) + (5 + 1) = 10。
因此，我們回傳它們的差值 10 - 6 = 4。
範例 2：
輸入： weights = [1, 3], k = 2
輸出： 0
解釋： 唯一可能的分配法為 [1],[3]。
由於最大和最小分數都一樣，因此我們回傳 0。
解題思維：
可以看到題目定義的分配法會等價於把 k - 1 個「棍子」插進 weights 中的數字。
例如說 weights = [1,2,3,4,5,6,7,8,9] 、 k = 4，則分配法可以表為如下（為了方便將忽略逗號和括號）：
1 | 2 3 4 | 5 6 7 | 8 9
其中「|」代表著棍子。而我們可以看到上面的分配法以範例測資的方式表示會是 [1] 、 [2,3,4] 、 [5,6,7] 、 [8,9]。
可以看到每一個分配法中的分數是「開頭數字」 + 「結尾數字」 + 「貼在每一根棍子兩側的數字」（例如說上例的「1 | 2」或「7 | 8」等）。
可以看到「開頭數字」和「結尾數字」會出現在「每一個」分配法之中，因此如果要算最大分數與最小分數的差值則可以直接忽略這兩個數字。
因此我們只需要考慮「貼在每一根棍子兩側的數字」要挑什麼。而把這些「棍子」移掉之後，可以看到這些數對就只是在 weights 中的相鄰數字而已。
因此如果要最小化分數，則我們要在 w - 1 對（w = weights.length）的相鄰數字總和中挑出 k - 1 個最小者，並加總便可以得到；同樣地，從 w - 1 對相鄰數字總和中挑出 k - 1 最大者加總之後即可得到最大分數。
此時兩者相減即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
