aao DP KARE Hindi me || DP EASY
Intuition\n Describe your first thoughts on how to solve this problem. \ndekho isme sum kitne pair ka equal h count karna h\niske liye 3 tarah ka kaam kar skate
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ndekho isme sum kitne pair ka equal h count karna h\n**iske liye** 3 tarah ka kaam kar skate h\n1.)pahle 2 ka sum\n2.)last 2 ka sum\n3.)pahle and last ka sum\n\nmaan lo pahle 2 ka sum liye uske baad sum maan lo last 2 k equal hua fir aage jaake last and first k equal hua.....aise chalte jaayega hume specifically nhi pata ki kon se 2 element ka sum equal hoga \niske liye hume all possible path try karna hoga \n**ALL POSSIBLE PATH ka matlab h RECURSION**\n\nAB SAMGH GAYE HONGE KI KYU RECURSION LAG RAHA H\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.)SABSE PAHLE HUM FIRST AND SECOND KA SUM K LIYE MAXIMUM PAIR KHOZUNGA\n2.)FIR USKE BAAD HUM FIRST AND LAST KA SUM K LIYE MAXIMUM PAIR KHOZENGE\n3.)FIR HUM USKE BAAD LAST 2 KA SUM K LIYE MAXIMUM PAIR KHOZENGE\nJO MAXIMUM PAIR DENGE WAHI ANSWER.\n\n**Ab hum isko kaise code likhenge**\n- hum ek start index lenge jo 0 se hoga\n- hum ek end index lenge jo last index se start hoga\n- uske baad hum ek karke 3 k liye recursive call karenge\n- **ab recursion function me hum kya likhnege code me dekhte h**\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    private:\n    int solve(vector<int>&nums,int start,int end,int sum,vector<vector<int>>&dp)\n    {\n        //agar start bada h end se toh hum 0 return karenge\n        if(start>=end)\n        {\n            return 0;\n        }\n        //memoization\n        if(dp[start][end]!=-1)\n        {\n            return dp[start][end];\n        }\n       \n        //first 2 sum k liye\n        int aage=0;\n        if(nums[start]+nums[start+1]==sum)\n        {\n            //agar sum k equal aata h to start ko jaha h waha se 2 \n            //aage badha do\n            aage=1+solve(nums,start+2,end,sum,dp);\n        }\n\n        //last 2 sum k liye\n        int piche=0;\n        if(nums[end]+nums[end-1]==sum)\n        {\n            //agar sum k equal aata h to hum end ko end-2 shift kar \n            //denge\n            piche=1+solve(nums,start,end-2,sum,dp);\n        }\n        \n        //aage piche elements ka sum k liye\n        int aagpic=0;\n        if(nums[start]+nums[end]==sum)\n        {\n            //agar eual h to start ko ek aage badha do and end ko ek \n            //piche\n            aagpic=1+solve(nums,start+1,end-1,sum,dp);\n        }\n        \n        //teeno me se jo maximum pair dega woh answer.\n        return dp[start][end]=max(aage,max(piche,aagpic));\n    }\npublic:\n    int maxOperations(vector<int>& nums) {\n        int n=nums.size();\n        //agr array me 2 hi element h toh 1 hi pair bana toh answer 1\n        if(n==2)\n        {\n            return 1;\n        }\n        int start=0;\n        int end=n-1;\n        \n        //vector for memoization\n        vector<vector<int>>dp(n,vector<int>(n,-1));\n        //first two elements ka sum\n        int sum1=nums[0]+nums[1];\n        //function call first 2 ka sum k liye\n        int ans1=solve(nums,start,end,sum1,dp);\n\n        \n        //vector for memoization\n        vector<vector<int>>dpp(n,vector<int>(n,-1));\n        //first and last element ka sum\n        int sum2=nums[0]+nums[n-1];\n        //function call first and last element ka sum k liye\n        int ans2=solve(nums,start,end,sum2,dpp);\n        \n        //vector for memoization\n        vector<vector<int>>dppp(n,vector<int>(n,-1));\n        //last two elements ka sum\n        int sum3=nums[n-1]+nums[n-2];\n        //function call last 2 element ka sum k liye\n        int ans3=solve(nums,start,end,sum3,dppp);\n        \n        //max teeno me se!!\n        return max(ans1,max(ans2,ans3));\n    }\n};\n```\n\n![upvote.webp](https://assets.leetcode.com/users/images/f97339a0-dbd7-48d6-b0cf-a4f6f7a69505_1708204185.8251758.webp)\n
['Array', 'Dynamic Programming', 'Memoization', 'C++']