C++ || Bottom-up DP || Beats 99% time and 97% memory
Regardless of the problem description, both the strategies of Alice and Bob are the same.\nMaximize the difference(From Bob\'s perspective, difference is define
Regardless of the problem description, both the strategies of Alice and Bob are the same.\n**Maximize the difference(From Bob\'s perspective, difference is defined as Bob\'s score - Alice\'s score) given the remaing stones**\n```\nint stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n\t\t// Initialize 2 arrays to swap in each iteration\n        int *diff = new int[n], *diff2 = new int[n];\n        memset(diff, 0, n*sizeof(int));\n\t\t\n\t\t// Calculate prefix sum in order to calculate range sums;\n        vector<int> prefix_sum(n+1, 0);\n        for (int i=1; i<=n; ++i)\n            prefix_sum[i] = stones[i-1] + prefix_sum[i-1];\n\t\t\n        for (int i=1; i<n; ++i) {\n            for (int j=0; j<n-i; ++j) {\n\t\t\t// new diff[j] would be:\n\t\t\t// max(result of choosing (j+i)th stone, result of choosing jth stone)\n\t\t\t// max(sum(j...j+i-1) - diff(j...j+i-1), sum(j+1...j+i) - diff(j+1...j+i))\n                diff2[j] = max((prefix_sum[j+i] - prefix_sum[j] - diff[j]), (prefix_sum[j+i+1] - prefix_sum[j+1] - diff[j+1]));\n            }\n            swap(diff, diff2);\n        }\n\t\t\n        return diff[0];\n    }\n```
[]