題目連結：
題目意譯：
現在有若干顆石頭排成一列，其中每一顆石頭上頭都各自寫著數字。而這些數字是以一個陣列 stoneValue 所給定。
在遊戲中的每一回合中，Alice 將會把這一列石頭分成兩個非空列（即，左側列和右側列），接著 Bob 將會計算兩列各自的數值，其中某一列的數值計算方法為該列的元素之總和。之後 Bob 將會把數值較大的那一列丟掉，而 Alice 的分數增加量會是剩下的那一列之數值。如果兩列的數值一樣，則 Bob 會讓 Alice 決定哪一列要被丟掉。而下一回合將會以剩餘的那一列作為開始。
在只剩下一顆石頭時，遊戲結束。Alice 的分數一開始為 0。
回傳 Alice 能獲得的最大分數值。
限制：
1 ≦ stoneValue.length ≦ 500
1 ≦ stoneValue[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： stoneValue = [6,2,3,4,5,5]
輸出： 18
解釋： 在第一回合中，Alice 將石頭分成 [6,2,3] 和 [4,5,5]。左側列之數值為 11 而右側列的數值為 14。Bob 把右側列丟掉，而現在 Alice 的分數為 11。
在第二回合中，Alice 將石頭分成 [6] 和 [2,3]。這次 Bob 將會丟掉左側列，並且 Alice 的分數變為 16（11 + 5）。
在最後一回盒中，Alice 只能將石頭分成 [2] 和 [3]。Bob 丟掉右側列，而 Alice 的分數現在是 18（16 + 2）。此時遊戲結束，因為只剩下一顆石頭了。
範例 2：
輸入： stoneValue = [7,7,7,7,7,7,7]
輸出： 28
範例 3：
輸入： stoneValue = [4]
輸出： 0
解題思維：
（令 n = stoneValue.length）
可以看到本題可以用和這題基本上一樣的想法來基於動態規劃（Dynamic Programming，DP）的精神解出。
定義一個陣列 D，其中 D[i][j] 代表著石頭只剩下 stoneValue[i]（含）～ stoneValue[j]（含）這幾顆（0 ≦ i ≦ j < n）時，Alice 可以獲得的最大分數。可以看到遞迴式為：
D[i][i] = 0
（注意剩一顆石頭是得不到分數的。而上式為遞迴停止條件。）
D[i][j] = max(P(k))，其中 i ≦ k < j，而 P(k) 定義如下：
當 S(i, k) < S(k + 1, j) 時，P(k) = D[i][k] + S(i, k)；
當 S(i, k) > S(k + 1, j) 時，P(k) = D[k + 1][j] + S(k + 1, j)；
以上皆非，則 P(k) = max(D[i][k] + S(i, k), D[k + 1][j] + S(k + 1, j))。
（即 i ～ k 為左側列，而 k + 1 ～ j 為右側列）
其中 S(x, y)（x ≦ y）代表著 stoneValue[x] + stoneValue[x + 1] + …… + stoneValue[y]。
可以看到所求為 D[0][n - 1] 之值。
根據上面連結之題目的 Bottom-up 方式求解的話，我們會窮舉出每一個可能的 (i, j) 滿足 0 ≦ i ≦ j < n 並且對於每一個數對 (i, j)，會窮舉出所有可能的 k 值滿足 i ≦ k < j。而要求出 S(x, y) 之值可以預先建立前綴和（Prefix Sums）並根據這題的作法在 O(1) 時間求出單一一個 S(x, y)。因此時間複雜度為「建立前綴和」+「DP 求解」= O(n) + O(n ^ 3) × O(1) = O(n ^ 3)。
但實際上我們可以做得更好。可以看到如果我們知道某個 C(i, j) 值使得
S(i, C(i, j)) ≦ S(C(i, j) + 1, j)
且
S(i, C(i, j) + 1) > S(i, j) ÷ 2
（即代表著左側列的數值在不超過右側列的數值之情況下，最多只能延伸到 C(i, j)）
則先前的 P(k) 實際上可以被簡化為
當 S(i, C(i, j)) < S(i, j) ÷ 2 時，P(k) = max(L[i][C(i, j)], R[C(i, j) + 2][j])
當 S(i, C(i, j)) == S(i, j) ÷ 2 時，P(k) = max(L[i][C(i, j)], R[C(i, j) + 1][j], R[C(i, j) + 2][j])
其中 L[x][y] 代表著「左側列」被 [x, y] 這個範圍包住且「沒有被丟掉的前提下」會得到多少分數；R[x][y] 也是類似，只是這邊是負責「右側列」。
可以看到 L[i][j] 和 R[i][j] 和 D[i][j] 有著類似的遞迴式。更準確地來說，我們有
L[i][i] = R[i][i] = stoneValue[i]；
L[i][j] = R[i][j] = 0，其中 i > j；
（上面二式為遞迴停止條件；i > j 的式子是為了方便起見，超出範圍應視為 0）
L[i][j] = max(L[i][j - 1], D[i][j] + S(i, j))，其中 i ≦ j；
R[i][j] = max(R[i + 1][j], D[i][j] + S(i, j))，其中 i ≦ j。
可以看到 L[i][j] 和 R[i][j] 可以完美地與求 D[i][j] 之 Bottom-up 過程合併在一起（即求完 D[i][j] 之後便可以更新 L[i][j] 和 R[i][j] 之值）。
因此此時 max(P(k)) 只需要 O(1) 時間算出。因此 DP 的部份變成了 O(n ^ 2)。
剩下的問題就是 C(i, j) 了。首先，我們可以觀察得到 C(i, j) ≦ C(i, j + 1) ≦ C(i, j + 2) ≦ ……
因此我們可以窮舉所有可能的 i 值並先算出 C(i, i + 1)。
然後 C(i, i + 2) 至少會是 C(i, i + 1)，因此從 C(i, i + 1) 往右擴張看看直到不能為止；然後 C(i, i + 3) 再繼承 C(i, i + 2)，並從該處往右擴張。重複此步驟直到 C(i, n - 1) 為止。
可以看到求出 C(i, i + 1) ～ C(i, n - 1) 只需要 O(n) 的時間。因為總體的「往右擴張」之次數最多只有 O(n) 次。而可能的 i 值有 O(n) 個，因此這部份的時間複雜度為 O(n ^ 2)。
因此「改良」後的演算法總體時間複雜度為「建立前綴和」+「建立 C(i, j)」+「DP 求解」= O(n) + O(n ^ 2) + O(n ^ 2) = O(n ^ 2)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
