C++ || Bawaal Question || Fully Explained Intuitions || Memoization || DP
\n// Bawwal Question \n    \n    // A -> only one element , ans = 0;\n    \n    // AB -> if we will remove A , we will take B \n            // if we will remove
```\n// Bawwal Question \n    \n    // A -> only one element , ans = 0;\n    \n    // AB -> if we will remove A , we will take B \n            // if we will remove B , we will take A , ans=max(A , B) in this case\n    \n    // ABC -> Case 1 if we will remove A , then it will be like B + C - max(func(BC))\n          // Case 2  If we will remove C , then it will be like A + C -max(func(AB))\n       // answer will be max(case1 , case2) in this .\n\t   \n\t     // ABCD-> Case 1 if we will remove A , then it will be like B + C + D - max(func(BCD))\n          // Case 2  If we will remove D , then it will be like A + B + C -max(func(ABC))\n\t\t  // answer will be max(case1 , case2) in this .\n    \n    // See there are 2 components First -> Adding B+C  , Second -> Substracting \n    \n    //max(its smaller subproblem) , First Components represents taking Alice sum by\n    //removing the value , Bob wants to minimise the diff thus by taking max value of \n    //its smaller problem(func(BC)) , Our answer will be max (of all the \n    //possibiliies) as Alice wants to maximise the diff of the scores , ans will be \n    //max( B + C - max(func(BC)) , A + C -max(func(AB)) ).    \n    \n    \n    int dp[1004][1004];\n    \n    \n    int func(vector<int> &nums , int i , int j , vector<int> &psum , int n)\n    {\n        if(i==j)\n        {\n            // only one stone left , so we have to remove it \n            // diff will be zero in this case \n            \n            return 0;\n        }\n        \n        if(dp[i][j]!=-1)\n        {\n            return dp[i][j];\n        }\n        \n        // Alice remove from left side \n        int Alice_pos1 = psum[j]-psum[i] - func(nums , i+1 , j , psum , n);\n        // this func calls which we a re substracting doing the job of BOb ,   \n        //(substracting maximal value of the smaller problem)\n        \n        // Alice removes from end\n        \n        int Alice_pos2 = psum[j-1]-psum[i]+nums[i] - func(nums , i , j-1 , psum , n);\n        \n        int ans=max(Alice_pos1 , Alice_pos2);// Alice wants will take max of 2 possibilty\n        \n        return dp[i][j]=ans;\n            \n    }\n    \n    int stoneGameVII(vector<int>& nums) {\n        \n          int n=nums.size();\n        \n          vector<int> psum(n , 0);\n        \n          psum[0]=nums[0];\n        \n          for(int i=1;i<n;i++)\n          {\n              psum[i]=psum[i-1]+nums[i];\n          }\n          \n           memset(dp , -1 , sizeof(dp));\n        \n          int res=func(nums , 0 , n-1 , psum , n );\n        \n          return res;\n          \n        \n    }\n```
['Dynamic Programming', 'Memoization', 'C']