There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice's is initially zero.

Return the maximum score that Alice can obtain.

&nbsp;
Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.


Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28


Example 3:

Input: stoneValue = [4]
Output: 0


&nbsp;
Constraints:


	1 &lt;= stoneValue.length &lt;= 500
	1 &lt;= stoneValue[i] &lt;= 106


from collections import defaultdict
from itertools import accumulate

class Solution:

    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        dp = [[0]*n for _ in range(n)]
        left = [[0]*n for _ in range(n)]
        prefix = list(accumulate(stoneValue))
        prefix = [0]+prefix+[prefix[-1]]

        def sum(i,j):
            return prefix[j+1]-prefix[i]

        row_idx = [i for i in range(n)]
        for i in range(n):
            left[i][i] = stoneValue[i]
        for d in range(1,n):
            for i in range(n-d):
                j = i+d
                while sum(i,row_idx[i]) < sum(row_idx[i]+1,j):
                    row_idx[i] +=1
                if sum(i, row_idx[i]) == sum(row_idx[i]+1,j):
                    dp[i][j] = max(left[i][row_idx[i]], left[j][row_idx[i]+1])
                else:
                    if row_idx[i] == i:
                        dp[i][j] = left[j][i+1]
                    elif row_idx[i] == j:
                        dp[i][j] = left[i][j-1]
                    else:
                        dp[i][j] = max(left[i][row_idx[i]-1], left[j][row_idx[i]+1])
                left[j][i] = max(left[j][i+1],sum(i,j)+dp[i][j])
                left[i][j] = max(left[i][j-1],sum(i,j)+dp[i][j])
        return dp[0][n-1]
class Solution {
    int dp[][];
    public int fnc(int a[], int i, int j, int sum){
        //System.out.println(i+" "+j);
        int n=a.length;
        if(i>j)
            return 0;
        if(j>n)
            return 0;
        if(i==j){
            dp[i][j]=-1;
            return 0;
        }
        if(dp[i][j]!=0)
            return dp[i][j];

   int temp=0;
        int ans=Integer.MIN_VALUE;

        for(int index=i;index<=j;index++){
            temp+=a[index];
            if(temp>sum-temp){
                ans=Math.max(ans,((sum-temp)+fnc(a,index+1,j,sum-temp)));
            }
            else if(temp<sum-temp){
                ans=Math.max(ans,temp+fnc(a,i,index,temp));
            }
            else
                ans=Math.max(ans,Math.max(sum-temp+fnc(a,index+1,j,sum-temp),temp+fnc(a,i,index,temp)));
        }
        dp[i][j]=ans;
        return dp[i][j];
    }
    public int stoneGameV(int[] stoneValue) {
        int n=stoneValue.length;
        int sum=0;
        for(int ele:stoneValue)
            sum+=ele;
        dp= new int[n][n];
        return fnc(stoneValue,0,n-1,sum);

    }
}
class Solution {
public:
    int dp[501][501];

    int f(vector<int> &v,int i,int j){

        if(i>=j) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        int r=0;
        for(int k=i;k<=j;k++) r+=v[k];

        int l=0,ans=0;
        for(int k=i;k<=j;k++){
            l+=v[k];
            r-=v[k];
            if(l<r) ans=max(ans,l+f(v,i,k));
            else if(r<l) ans=max(ans,r+f(v,k+1,j));
            else ans=max(ans,max(l+f(v,i,k),r+f(v,k+1,j)));
        }
        return dp[i][j]=ans;
    }

    int stoneGameV(vector<int>& stoneValue) {

        memset(dp,-1,sizeof(dp));
        return f(stoneValue,0,stoneValue.size()-1);

    }
};
var stoneGameV = function(stoneValue) {
    // Find the stoneValue array's prefix sum
    let prefix = Array(stoneValue.length).fill(0);
    for (let i = 0; i < stoneValue.length; i++) {
        prefix[i] = stoneValue[i] + (prefix[i - 1] || 0);
    }

    let dp = Array(stoneValue.length).fill().map(() => Array(stoneValue.length).fill(0));

    function game(start, end) {
        if (dp[start][end]) return dp[start][end];
        if (start === end) return 0;

        let max = 0;
        for (let i = start + 1; i <= end; i++) {
            let sumL = prefix[i - 1] - (prefix[start - 1] || 0);
            let sumR = prefix[end] - (prefix[i - 1] || 0);
            if (sumL > sumR) {
                max = Math.max(max, sumR + game(i, end));
            } else if (sumL < sumR) {
                max = Math.max(max, sumL + game(start, i - 1));
            } else {
                // If tied, check both rows
                let left = sumR + game(i, end);
                let right = sumL + game(start, i - 1);
                max = Math.max(max, left, right);
            }
        } return dp[start][end] = max;
    }

    return game(0, stoneValue.length - 1);
};
Stone Game V