Easy Approach || Recursive Approach with Memoization || C++ || Please Upvote
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem aims to find the maximum number of operations that can be performed on a gi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem aims to find the maximum number of operations that can be performed on a given array of integers, where each operation involves selecting two elements from the array that sum up to a certain value. Here\'s the intuition behind the solution:\n\n1. We can solve this problem using a recursive approach combined with memoization (dynamic programming).\n2. At each step, we consider various segment configurations of the array and try to maximize the number of operations that can be performed.\n3. We keep track of the maximum number of operations that can be performed for each segment configuration using a memoization table.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n-> Recursive Approach with Memoization:\n\n1. We define a recursive function solve that takes the current left and right indices of the array segment being considered, the target sum s, the array nums, and a memoization table dp.\n2. Base case: If the segment contains zero or one element (left >= right), the answer is 0.\n3. If the answer for the current segment [left, right] has already been calculated, it is directly returned from the memoization table.\n4. We consider three possibilities for selecting pairs:\nOne with the left index (a).\nOne with the right index (b).\nOne with both (c).\n5. Recursively, we check if pairs can be formed at different segment configurations by adjusting the indices and update the memoization table.\n6. Finally, we return the maximum number of operations that can be performed for the current segment.\n\n-> Main Function maxOperations:\n\n1. We initialize three memoization tables corresponding to different segment configurations.\n2. We calculate the initial values of segment sums based on different pairs.\n3. We invoke the solve function for each segment configuration to compute the maximum number of operations. \n4. We take the maximum of these three results as the final answer.\n5. Since the question asks for the maximum number of operations, we add 1 to the final answer before returning it.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$ \n\n- Space complexity:\n$$O(n^2)$$ \n\n# Code\n```\nclass Solution {\npublic:\n    int solve(int left, int right, int s, vector<int>&nums, vector<vector<int>>&dp)\n    {\n        if(left>=right)\n        {\n            return 0;\n        }\n        \n        if(dp[left][right]!=-1)\n        {\n            return dp[left][right];\n        }\n        \n        int a=0;\n        int b=0;\n        int c=0;\n        \n        if(left+1<=right && nums[left]+nums[left+1]==s)\n        {\n            a=1+solve(left+2,right,s,nums,dp);\n        }\n        \n        if(right-1>=left && nums[right]+nums[right-1]==s)\n        {\n            b=1+solve(left,right-2,s,nums,dp);\n        }\n        \n        if(nums[left]+nums[right]==s)\n        {\n            c=1+solve(left+1,right-1,s,nums,dp);\n        }\n        \n        return dp[left][right] = max(a,max(b,c));\n    }\n    int maxOperations(vector<int>& nums) {\n        int n=nums.size();\n        vector<vector<int>>dp1(n+1,vector<int>(n+1,-1));\n        vector<vector<int>>dp2(n+1,vector<int>(n+1,-1));\n        vector<vector<int>>dp3(n+1,vector<int>(n+1,-1));\n        \n        int s1=nums[0]+nums[1];\n        int s2=nums[0]+nums[n-1];\n        int s3=nums[n-2]+nums[n-1];\n        \n        int a=solve(2,n-1,s1,nums,dp1);\n        int b=solve(0,n-3,s3,nums,dp2);\n        int c=solve(1,n-2,s2,nums,dp3);\n        \n        int ans = max(a,max(b,c));\n        ans++;\n        \n        return ans;\n        \n        \n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']