Javascript Memoization with clear code
The main point is spotting the subproblem.\n\nOptimal diff with array between i, j = Max(\n    Score when i + 1 is removed - Optimal diff with array between i +
The main point is spotting the subproblem.\n\nOptimal diff with array between i, j = Max(\n    Score when i + 1 is removed - Optimal diff with array between i + 1,j,\n    Score when j - 1 is removed - Optimal diff with array between i, j - 1\n);\nIts a simple recursion equation at this point, and there would be alot of duplicate calls so better apply memoization.\n\n```js\n/**\n * Returns sum between start index & end index\n */\nconst getSum = (start, end, prefixSums) => {\n    return prefixSums[end + 1] - prefixSums[start];\n}\n\n/**\n * calculates optimal diff between start index & end index\n **/\nconst calculateDiff = (start, end, prefixSums, dp) => {\n    if (start === end) {\n        // if start & end is the same diff would always be 0 as the player would remove the stone and score won\'t change.\n        return 0;\n    }\n\n    if (!dp[start]) {\n        dp[start] = [];\n    }\n\n    if (!dp[start][end]) {\n        dp[start][end] = Math.max(\n            getSum(start + 1, end, prefixSums) - calculateDiff(start + 1, end, prefixSums, dp),\n            getSum(start, end - 1, prefixSums) - calculateDiff(start, end - 1, prefixSums, dp)\n        );\n    }\n\n    return dp[start][end];\n}\n\n/**\n * @param {number[]} stones\n * @return {number}\n */\nvar stoneGameVII = function(stones) {\n    // First calculate prefix sums\n    const prefixSums = [0];\n    for (let i = 1;i <= stones.length;i++) {\n        prefixSums[i] = stones[i - 1] + prefixSums[i - 1];\n    }\n\n    // Now calculate optimal diff between 0 and stones.length - 1\n    return calculateDiff(0, stones.length - 1, prefixSums, []);\n};\n```
[]