c++||DP||easy solution||Memoization
Intution\nthis is a dynamic programming problem because at every point we have to make 3 choices and take the max out of it\n Describe your first thoughts on ho
# Intution\nthis is a dynamic programming problem because at every point we have to make 3 choices and take the max out of it\n<!-- Describe your first thoughts on how to solve this problem. -->\n# Approach\n**Utilizing Dynamic Programming with Memoization**: This problem lends itself well to an efficient solution through dynamic programming with memoization. We devise a recursive function to explore various pairs of elements, maintaining the maximum number of operations for each selection.\n\n**Recurrence Relation**: Our function\'s recurrence relation examines three scenarios: selecting the first two elements, choosing the first and last elements, and opting for the last two elements. For each scenario, we compute the maximum number of operations possible and select the highest among them.\n\n**Memoization**: Employing a 2D memoization array, we store computed results of subproblems. Before evaluating the maximum operations for a particular subarray, we verify if it\'s been previously calculated. If so, we retrieve the result from the memoization table, eliminating redundant computations.\n\n**Base Cases**: We address scenarios where the subarray consists of only one or no elements. In such instances, the maximum number of operations achievable is zero.\n\n**Main Function**: Within the main function, we initialize the memoization array and invoke the recursive function for each of the three cases: selecting the first two elements, picking the first and last elements, and choosing the last two elements. Subsequently, we return the maximum number of operations among these three scenarios\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\nTime complexity:\nThis approach\'s time complexity stands at O(n^2), where n represents the number of elements in the input array. This is primarily due to the n * n dimensions of the memoization table, with each entry computed once.\n\nSpace complexity:\nThe space complexity also amounts to O(n^2) owing to the memoization table storing subproblem results. Furthermore, in the worst-case scenario, the recursive stack may extend up to O(n) levels. Consequently, the predominant factor in space complexity remains the memoization table.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>>dp;\n    int solve(int l,int r,int score,vector<int>&nums)\n    {\n        if(l>=r)return 0;\n        if(dp[l][r]!=-1)return dp[l][r];\n        \n        int ans=0;\n        if(nums[l]+nums[l+1]==score)ans=max(ans,1+solve(l+2,r,score,nums));\n        if(nums[r]+nums[r-1]==score)ans=max(ans,1+solve(l,r-2,score,nums));\n        if(nums[l]+nums[r]==score)ans=max(ans,1+solve(l+1,r-1,score,nums));\n        \n        return dp[l][r]=ans;\n    }\n    int maxOperations(vector<int>& nums) {\n        dp.resize(nums.size()+1,vector<int>(nums.size()+1,-1));\n        int n=nums.size();\n        int ans=0;\n        ans=max(ans,1+solve(2,n-1,nums[0]+nums[1],nums));\n        ans=max(ans,1+solve(0,n-3,nums[n-1]+nums[n-2],nums));\n        ans=max(ans,1+solve(1,n-2,nums[0]+nums[n-1],nums));\n        return ans;\n    }\n};\n```
['C++']