C++ Fully Explained | Without Prefix Sum
There is no need to calculate prefix sum.\nFor.eg. Let\'s say the array is\n    a1, a2, a3, a4\n\nNow consider alice picks a1\n    Again consider bob picks a2, 
There is no need to calculate prefix sum.\nFor.eg. Let\'s say the array is\n    a1, a2, a3, a4\n\nNow consider alice picks a1\n    Again consider bob picks a2, then diff will be\n        (a2 + a3 + a4) - (a3 + a4) = a2\n        i.e. the element which bob picked.\n\nIt can also be checked for others that the difference\nwill always be the value that bob picked.\n\n```\nstruct Solution {\n    \n    int n, *a;\n    int dp[1000][1000];\n    \n    int f(int i, int j) {\n        \n        if (i >= j) return 0;\n        \n        if (dp[i][j] != -1) return dp[i][j];\n/*\n        Alice will try to maximize and bob will try to minimize.\n        Hence result will be\n        max(f(i+1, j), f(i, j-1))\n        i.e. max of if she pick left most, or if she pick right most\n\n        if alice picks left most (i.e. i)\n            then bob can pick either i+1 or j\n        i.e. f(i+1, j) will be min( f(i+2, j) + a[i+1], f(i+1, j-1) + a[j] )\n        \n        \n        if alice picks right most (i.e. j)\n            then bob can pick either i or j-1\n        i.e. f(i, j-1) will be min( f(i+1, j-1) + a[i], f(i, j-2) + a[j-1] )\n*/\n        return dp[i][j] = max(\n            min( f(i+2, j) + a[i+1], f(i+1, j-1) + a[j] ),\n            min( f(i+1, j-1) + a[i], f(i, j-2) + a[j-1] ));\n    }\n\n    int stoneGameVII(vector<int> &a) {\n        \n        memset(dp, -1, sizeof dp);\n        \n        this->a = a.data();\n        this->n = a.size();\n        \n        return f(0, n-1);\n    }\n};\n```\nCleaned Solution\n```\nstruct Solution {\n    \n    int n, *a;\n    int dp[1000][1000];\n    \n    int f(int i, int j) {\n        \n        if (i >= j) return 0;\n        \n        if (dp[i][j] != -1) return dp[i][j];\n\n        return dp[i][j] = max(\n            min( f(i+2, j) + a[i+1], f(i+1, j-1) + a[j] ),\n            min( f(i+1, j-1) + a[i], f(i, j-2) + a[j-1] ));\n    }\n\n    int stoneGameVII(vector<int> &a) {\n        \n        memset(dp, -1, sizeof dp);\n        \n        this->a = a.data();\n        this->n = a.size();\n        \n        return f(0, n-1);\n    }\n};\n```\n\nTC: O(n\xB2)\nSC: O(n\xB2) (It can be optimized using Tabulation to O(n))\n\nPS: Upvote if found helpful :)
[]