Java O(n^2) bottom up solution with detailed explanation. No prefix sum
Considering array [a1,a2,...,an-1,an]\n\nIf Alice takes a1, then Alice gains sum(a2,...,an) score. Bob takes either a2 or an, which gives him either sum(a3,...,
Considering array [a1,a2,...,an-1,an]\n\nIf Alice takes `a1`, then Alice gains `sum(a2,...,an)` score. Bob takes either `a2` or `an`, which gives him either `sum(a3,...,an)` score or `sum(a2,...,an-1)` score, hence the difference is either `a2` or` an`. Since Bob wants to minimize the difference, he should take  `min(a2, an)` given Alice took `a1`.\n\nIf Alice takes `an`, following a similar deduction, Bob should take `min(a1, an-1)` given Alice took `an`.\n\nNow that Alice want to maximize the difference, she should gain  `max(min(a2, an), min(a1, an-1))`. \n\nThen they are back to the same problem with a smaller size.\n\nTo sum up, let\'s use `dp[i][j]` to represent the differece of their score for array `[ai,...aj]` if they both play optimally.\nThe initial state `dp[i][i]` is 0 since if Alice takes the only element she gains 0 score and so is Bob. `dp[i][i+1]` is `max(ai, ai+1)` since Alice must take the smaller element to gain the larger element\'s score. \nThe transfer equation is \n`dp[i][j]=max(`\n`min(dp[i+2][j]+a2 , dp[i+1][j-1]+an), ` when Alice takes a1\n`min(dp[i+1][j-1]+a1, dp[i][j-2]+an-1)` when Alice takes an\n`)`\n\n```\nclass Solution {\n    public int stoneGameVII(int[] s) {\n        int n = s.length;\n        if(n==2) return Math.max(s[0],s[1]);\n        int[][] dp = new int[n][n];\n\t\t// initial state setup\n        for(int i=0; i<n-1; i++) {\n            dp[i][i+1] = Math.max(s[i],s[i+1]);\n        }\n\t\t// start from length 3, since length 2 is setup as initial state\n        for(int len=3; len<=n; len++) {\n            for(int i=0; i+len-1<n; i++) {\n                int j = i+len-1;\n\t\t\t\t// if Alice takes left most stone\n                int m1 = Math.min(dp[i+1][j-1]+s[j], dp[i+2][j]+s[i+1]);\n\t\t\t\t// if Alice takes right most stone\n                int m2 = Math.min(dp[i+1][j-1]+s[i], dp[i][j-2]+s[j-1]);\n\t\t\t\t// choose the larger one\n                dp[i][j] = Math.max(m1, m2);\n            }\n        }\n        return dp[0][n-1];\n    }\n}\n```
[]