Python 3, today's one-liner
Explanation\n\nFairly typical Memo/DP problem, with a tricky bit on how you handle sums.\n\nYou can define a recursive function with arguments f(a, b) as the in
# Explanation\n\nFairly typical Memo/DP problem, with a tricky bit on how you handle sums.\n\nYou can define a recursive function with arguments `f(a, b)` as the indexes in the array, inclusive:\n1. `f(a, b)` is `0` if `a == b`\n2. `f(a, b)` is max of:\n    1. `sum(a+1, b) - f(a+1, b)` - your score if you remove the left stone\n    2. `sum(a, b-1) - f(a, b-1)` - your score if you remove the right stone\n\nAlso remember that if we have `T = accumulate(A, initial=0)`, then `sum(a, b) == T[b+1] - T[a]`.\n* This makes computing a sum an `O(1)` time calculation instead of `O(n)` time, given we spend `O(n)` time and space up front.\n\nOk, we have all we need to write a memoized function!\n\n# Memoized (top-down)\n\nTime: `O(n^2)`\nSpace: `O(n^2)`\n\n**But it times out! :(**\n\n```python\nclass Solution:\n  def stoneGameVII(self, A):\n    T = list(accumulate(A, initial=0))\n    \n    @cache\n    def f(a, b):\n      return a < b and max(\n        T[b+1] - T[a+1] - f(a+1, b),\n        T[b] - T[a] - f(a, b-1)\n      )\n    \n    return f(0, len(A) - 1)\n```\n\n# DP (bottom-up)\n\nMemoized times out, so we need a new approach.\n\nConvert it to DP... calculate the values bottom-up.\n\nTime: `O(n^2)`\nSpace: `O(n^2)`\n\n**It passes... ~6000 ms**\n\n```python\nclass Solution:\n  def stoneGameVII(self, A):\n    T = list(accumulate(A, initial=0))\n    dp = defaultdict(int)\n    for diff in range(1, len(A)):\n      for a in range(len(A) - diff):\n        b = a + diff\n        dp[a, diff] = max(\n          T[b+1] - T[a+1] - dp[a+1, diff-1],\n          T[b]   - T[a]   - dp[a, diff-1]\n        )\n    return dp[0, len(A)-1]\n```\n\n# DP, optimized (bottom-up)\n\nIf we rethink things a little, we only need `O(n)` space instead of `O(n^2)` if we build it row by row.\n\nSwitch to a 1D array instead of a 2D array.\n\nTime: `O(n^2)`\nSpace: `O(n)`\n\n**Even better... 2700-3000 ms**\n\n```python\nclass Solution:\n  def stoneGameVII(self, A):\n    T = list(accumulate(A, initial=0))\n    dp = [0] * len(A)\n    for diff in range(1, len(A)):\n      for a in range(len(A) - diff):\n        b = a + diff\n        dp[a] = max(\n          T[b+1] - T[a+1] - dp[a+1],\n          T[b]   - T[a]   - dp[a]\n        )\n    return dp[0]\n```\n\n# One line\n\nFinally, the reason you came here.\n\nIt\'s easy to build the DP array using a `reduce`, so lets do that.\n\nAlso wrap with an anonymous lamdba so we can pass in the `T` sums.\n\nTime & Space: same\n\n**Still 2700-3000 ms**\n\n```python\nclass Solution:\n  def stoneGameVII(self, A):\n    return (lambda *T: reduce(lambda dp,b: [max(T[a+b+1] - T[a+1] - dp[a+1], T[a+b] - T[a] - dp[a]) for a in range(len(A) - b)], range(1, len(A)), [0] * len(A))[0])(*accumulate(A, initial=0))\n```\n
[]