Easy || Intuitive || Try all possible ways || C++ Memoisation
Intuition\nThere are 3 possible ways to make a move, so we will try each move one-by-one.\n\n# Code\ncpp []\nclass Solution {\nprivate:\n    int solve(vector<in
# Intuition\nThere are 3 possible ways to make a move, so we will try each move one-by-one.\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int solve(vector<int> &nums, int left, int right, int last, vector<vector<int>> &dp){\n        if(left>=right) return 0;\n        if(right-left==1) return (nums[left] + nums[right] == last);\n\n        if(dp[left][right]!=-1) return dp[left][right];\n\n        int sum1 = nums[left] + nums[left+1];\n        int opt1 = 0;\n        if(sum1==last) opt1 = 1 + solve(nums, left+2, right, last, dp);\n\n        int sum2 = nums[right] + nums[right-1];\n        int opt2 = 0;\n        if(sum2==last) opt2 = 1 + solve(nums, left, right-2, last, dp);\n\n        int sum3 = nums[left] + nums[right];\n        int opt3 = 0;\n        if(sum3==last) opt3 = 1 + solve(nums, left+1, right-1, last, dp);\n\n        return dp[left][right] = max(opt1, max(opt2, opt3));\n    }\npublic:\n    int maxOperations(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<int>> dp1(n, vector<int>(n, -1));\n        vector<vector<int>> dp2(n, vector<int>(n, -1));\n        vector<vector<int>> dp3(n, vector<int>(n, -1));\n        \n        int left = 0, right = n-1;\n        int sum1 = nums[left] + nums[left+1];\n        int opt1 = 1 + solve(nums, left+2, right, sum1, dp1);\n\n        \n        int sum2 = nums[right] + nums[right-1];\n        int opt2 = 1 + solve(nums, left, right-2, sum2, dp2);\n\n        int sum3 = nums[left] + nums[right];\n        int opt3 = 1 + solve(nums, left+1, right-1, sum3, dp3);\n\n        return max(opt1, max(opt2, opt3));\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']