Simple 2D dp solution in cpp with proper explanation
Create dp[l][r] to count the pairs having a specific sum covering the array from index l to r.\nfor transition dp[i][j] will be max of all the three posibilitie
Create dp[l][r] to count the pairs having a specific sum covering the array from index l to r.\nfor transition dp[i][j] will be max of all the three posibilities, i.e\nselect first two elements that is 1+dp[i+2][j]\nselect last two elements that is 1+dp[i][j-2]\nand select one element from start and one from last 1+dp[i+1][j-1]\ndp[i][j] will be max of these three..\nnow use this function as black box to calculate for sum arr[0]+arr[1],arr[n-1]+arr[n-2] and arr[0]+arr[n-1].\nfinal answer will be the max of all three functions..\n\nnote: you can avoid three different dp arrays by just creating one array of dp[l][r][3]\n\n```\nclass Solution {\npublic:\n    \n    int solve(int l,int r,int sum,vector<int>&nums,vector<vector<int>>&dp)\n    {\n        if(l>=r)\n        {\n            return 0;\n        }\n        if(dp[l][r]!=-1)\n        {\n            return dp[l][r];\n        }\n        int mx=0;\n        if(nums[l]+nums[r]==sum)\n        {\n            mx=max(mx,1+solve(l+1,r-1,sum,nums,dp));\n        }\n        if(nums[l]+nums[l+1]==sum)\n        {\n            mx=max(mx,1+solve(l+2,r,sum,nums,dp));\n        }\n        if(nums[r-1]+nums[r]==sum)\n        {\n            mx=max(mx,1+solve(l,r-2,sum,nums,dp));\n        }\n        return dp[l][r]=mx;\n    }\n    \n    int maxOperations(vector<int>& nums) {\n        int n=nums.size();\n        vector<vector<int>>dp(n+1,vector<int>(n+1,-1));\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        int mx=1+solve(1,n-2,nums[0]+nums[n-1],nums,dp);\n        mx=max(mx,1+solve(2,n-1,nums[0]+nums[1],nums,dp1));\n        mx=max(mx,1+solve(0,n-3,nums[n-1]+nums[n-2],nums,dp2));\n        return mx;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']