题目分析

本题首先规定了游戏规则如下：

1. 将当前余下的石头分成左右非空的两部分；
2. 分别计算两部分的石头价值总和，若两者不等，则保留总和较小的一部分，否则任选一部分保留；
3. 将留下的石子价值总和计入$Alice$的得分；

按照上述规则一直进行游戏，直到只剩下一个石子为止。求$Alice$的最大得分。

基本思路

如果进行了一次分割，那么无论最终留下哪一部分，其实问题都变成了一个规模更小但相似的子问题，故可以想到用动态规划进行解决，定义动态规划数组$dp$，其中$dp[i][j]$表示在区间$[i,j)$中$Alice$能够取得的最大得分，那么将$k$在$(i,j)$中遍历，则$dp[i][j]$的计算需要分以下两种情况：

为方便叙述，记$stoneValues[i:k]$的总和为$left$，$stoneValues[k:j]$的总和为$right$。

不难发现，由于$stoneValues$中的所有值都是正数，那么随着$k$的增加，$left$必定越来越大，$right$必定越来越小，故一定存在下标$p$，使得当$k\in (i,p]$时均满足$left\leq right$，同理，一定存在下标$q$，使得当$k \in [q,j)$时均满足$left \geq right$，可以发现，当存在一个$k$使得$left=right$时，$q=p$，否则，$q=p+1$。

因此，如果用前缀和数组$s$表示出$left$和$right$，并结合上述分析即可得到：

将与$k$无关的项提取出来即可得到：

可以发现，后面求最大值的项中，$k$都是在区间$[i,j]$的前缀或后缀中遍历的，故如果能维护一个特定区间中指定式子的前缀最大值和后缀最大值，就可以快速求出$dp[i][j]$的值，定义前缀最大值数组$preMax[i][j]$表示$\max\limits_{k=i+1}^{j}(dp[i][k]+s[k])$，同时定义后缀最大值数组$sufMax[i][j]$表示$\max\limits_{k=i}^{j-1}(dp[k][j]-s[k])$，那么上面的递推关系式就变成了：

同时根据定义可以得知$preMax$和$sufMax$数组的递推关系如下：

有了递推关系式，接下来就需要确定区间左右端点遍历的顺序，注意到，在计算$preMax$的值时，位置$(i,j)$是由位置$(i,j-1)$转移过来的，说明$j$的遍历应当从前往后遍历，同时在计算$sufMax$的值时，位置$(i,j)$是由位置$(i+1,j)$转移过来的，说明$i$的遍历应当从后往前遍历。不过需要注意的是，并不是两个数组中的值都需要在$dp[i][j]$计算完毕后才更新，因为在计算$dp[i][j]$时，实际上需要用到一个$preMax[i][p]$，而$p$是在$i$之后的，故应当在向后计算$p$的位置时同步更新$preMax$中的值。

最后在$dp$中所有值计算完毕后，返回$dp[0][n]$即为答案。

实现细节

如果对于每一个区间都用遍历去寻找$p$和$q$的位置，时间复杂度则会到达$O(n^3)$，故需要将其简化，注意到当确定区间左端点$i$之后，由于$j$的遍历顺序是从前往后，因此$p$和$q$的位置一定是不断右移的，故对于每一个固定$i$的循环，都可以初始化一个$p$的位置，随着$j$的增加，每次都用while循环增加$p$直到满足要求，这样，对于每一个不同的$i$，$p$最多也就循环$n$次，而非暴力的$n^2$次，复杂度即可降为$O(n^2)$。

同时，由于$sufMax$数组是从后向前处理的，故而需要单独用一个二维数组保存，并且对于每一个不同的$i$都要初始化一个$sufMax[i][i+1]=dp[i][i+1]-s[i]=-s[i]$，作为它之后计算的依据。而$preMax$则可以压缩成一个数字，每次按顺序维护即可。

复杂度

时间复杂度：$O(n^2)$； 空间复杂度：$O(n^2)$。

代码

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        # 当k∈[i+1,p]中时，dp[i][j] = max(dp[i][k]+preSum[k]-preSum[i]) = -preSum[i]+max(dp[i][k]+preSum[k])
        # 当k∈[q,j]中时，dp[i][j] = max(dp[k][j]+preSum[j]-preSum[k]) = preSum[j]+max(dp[k][j]-preSum[k])
        n = len(stoneValue)
        dp = [[0]*(n+1) for _ in range(n)]
        preSum = [0]*(n+1)
        for i in range(n):
            preSum[i+1] = preSum[i]+stoneValue[i]
        sufMax = [[-10**18]*(n+1) for _ in range(n+1)] # 倒序处理，需要用二维数组保存

        for i in range(n-1, -1, -1):
            sufMax[i][i+1] = -preSum[i] # 初始化当前sufMax计算基准
            k = i+1 # 题目要求分出来的左右部分不能为空，故k最小为i+1
            preMax = 0 # 动态维护一个数字即可
            for j in range(i+2, n+1): # 题目要求分出的右边不能为空，故j最小为i+2，需要留两个位置
                while preSum[k]-preSum[i] <= preSum[j]-preSum[k]:
                    preMax = max(preMax, dp[i][k]+preSum[k]) # 它需要一直更新到k
                    k += 1
                # 结束时必有：preSum[k]-preSum[i] > preSum[j]-preSum[k]
                # 且preMax处理到k-1，恰好为论述中的preMax[i][p]
                q = k # k为p+1，如果k倒退一个位置使得两边和相等，那么q就应当为p，即k-1
                if preSum[k-1]-preSum[i] == preSum[j]-preSum[k-1]:
                    q -= 1
                dp[i][j] = max(dp[i][j], -preSum[i]+preMax, preSum[j]+sufMax[q][j])
                sufMax[i][j] = max(sufMax[i+1][j], dp[i][j]-preSum[i]) # 维护sufMax数组
        return dp[0][n]