主題
題目連結：
題目意譯：
你被給定一個長度為 n 的正整數陣列 nums。
一個多邊形為一個擁有至少三條邊的封閉平面圖形。一個多邊形的最長邊必定小於其他邊長之總和。
反過來說，如果你有 k（k ≧ 3）個正實數 a1, a2, a3, ……, ak，其中 a1 ≦ a2 ≦ a3 ≦ …… ≦ ak 且 a1 + a2 + a3 + …… + ak-1 > ak，其必定存在著一個有著 k 個邊的多邊形，其邊長為 a1, a2, a3, ……, ak。
一個多邊形的周長為其邊長之總和。
回傳邊長可以從 nums 中湊得的所有多邊形中最長之周長。如果不可能從 nums 中造出多邊形，則回傳 -1。
限制：
3 ≦ n ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [5,5,5]
輸出： 15
解釋： 唯一一個可能的多邊形為 3 條邊的：5 、 5 和 5。周長為 5 + 5 + 5 = 15。
範例 2：
輸入： nums = [1,12,1,2,5,50,3]
輸出： 12
解釋： 周長最長的多邊形可以由 5 條邊組成：1 、 1 、 2 、 3 和 5。周長為 1 + 1 + 2 + 3 + 5 = 12。
我們無法造出一個最長邊為 12 或 50 的多邊形，因為不可能塞入更多長度較短的邊使得較短邊總和大於最長邊。
可以證明最大可能的周長為 12。
範例 3：
輸入： nums = [5,5,50]
輸出： -1
解釋： 不可能從 nums 中形成多邊形，因為一個多邊形至少有 3 條邊而 50 > 5 + 5。
解題思維：
可以看到如果有一個數字 X 可以作為某多邊形的最長邊長，則把所有小於等於 X 的數字連同 X 一起作為邊長必定也可以形成一個多邊形。而很明顯地，這樣子可以最大化最長邊長為 X 的多邊形之周長。
因此我們可以把 nums 中的數字由小排到大，然後從最大的數字開始試可不可以形成多邊形。也就是說對於 nums[i] 判斷 nums[0] + nums[1] + …… + nums[i - 1] 有沒有大過 nums[i]。
而要算出 nums[0] + nums[1] + …… + nums[i - 1] 可以使用前綴和（Prefix Sum）計算，又或是觀察 nums[i + 1] 和 nums[i] 所需的數字。可以看到前者需要 nums[0] + nums[1] + …… + nums[i - 1] + nums[i] 而後者則是 nums[0] + nums[1] + …… + nums[i - 1]，兩者只差 nums[i]。又加上我們是從大的數字開始掃過，因此從 nums[i + 1] 走到 nums[i] 時 nums[i] 可以「繼承」 nums[i + 1] 的總和並減去 nums[i] 即可。
而第一個找到符合條件的 nums[i] 便是可以最大化所求周長的多邊形最長邊長，所求即為 nums[0] + nums[1] + …… + nums[i]；而掃完所有數字後發現都不能形成多邊形，則回傳 -1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
