C++ || TWO METHODS || RECURSION + MEMOIZATION || BOTTOM-UP DP
METHOD --> 1 \n\nint dp[1005][1005];\n    \n    int func(vector&nums,vector&prefix,int i,int j){\n        \n        if(i>=j){\n            return 0;\n        }\
# **METHOD --> 1 **\n\nint dp[1005][1005];\n    \n    int func(vector<int>&nums,vector<int>&prefix,int i,int j){\n        \n        if(i>=j){\n            return 0;\n        }\n        \n        if(dp[i][j]!=-1){\n            return dp[i][j];\n        }\n        \n        return dp[i][j]=max(prefix[j+1]-prefix[i+1]-func(nums,prefix,i+1,j) , prefix[j]-prefix[i]-func(nums,prefix,i,j-1));\n        \n        \n    }\n    \n    int stoneGameVII(vector<int>& stones) {\n        \n        int n=stones.size();\n        \n        memset(dp,-1,sizeof(dp));\n        \n        vector<int>prefix(n+1,0);\n        \n        for(int i=1;i<=n;i++){\n            prefix[i]=prefix[i-1]+stones[i-1];\n        }\n        \n        return func(stones,prefix,0,n-1);\n        \n    }\n\t\n\t\n# **\tMETHOD --> 2**\n\t\n\tint stoneGameVII(vector<int>& nums) {\n        \n        int n=nums.size();\n        \n        vector<int>prefix(n+1,0);\n        \n        for(int i=1;i<=n;i++){\n            prefix[i]=prefix[i-1]+nums[i-1];\n        }\n        \n        vector<vector<int>>dp(n,vector<int>(n,0));\n        \n        for(int i=0;i<n-1;i++){\n            dp[i][i+1]=max(nums[i],nums[i+1]);\n        }\n        \n        for(int L=3;L<=n;L++){\n            \n            \n            for(int i=0;i<n-L+1;i++){\n                \n                int j=i+L-1;\n                \n                int val1=prefix[j+1]-prefix[i+1]-dp[i+1][j];\n                int val2=prefix[j]-prefix[i]-dp[i][j-1];\n                \n                dp[i][j]=max(val1,val2);\n                \n            }\n            \n            \n        }\n        \n        return dp[0][n-1];\n        \n    }
[]