Beats 100%🔥Top down approach || DP with memoization✅ C++ || Java || Python3
Intuition\nWe need to check all possibilies:\n1. If the first two numbers add up to score.\n2. If the last two numbers add up to score.\n3. If the first and las
# Intuition\nWe need to check all possibilies:\n1. If the first two numbers add up to score.\n2. If the last two numbers add up to score.\n3. If the first and last number add up to score.\n\nWhenever we have to look for all the possibilites, recursive dp can be helpful.\n\n# Approach\nWe would require a 2D DP where the state variables would be the starting index and ending index of the array.\nWe then check for all the 3 possibilities and take the maximum of all three of them.\n\n**For case 1:** \nWe increment the starting index $$l$$ by 2 and pass the score as the addition of the first two numbers.\n\n**For case 2:** \nWe decrement the ending index $$r$$ by 2 and pass the score as the addition of the first two numbers.\n\n**For case 3:** \nWe increment the starting index $$l$$ by 1 and decrement the ending index $$r$$ by 1 and pass the score as the addition of the first two numbers.\n\nFor all the possibilities, we increment the value returned by function by 1 because we conside it as one operation.\n\nFor the recursion function, the base case would be when $$l>=r$$. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n\n    int func(int l, int r, vector<int> &nums, int num){\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] == num){\n            ans = max(ans, 1+func(l+2, r, nums, num));\n        }\n        if(nums[r]+nums[r-1] == num){\n            ans = max(ans, 1+func(l, r-2, nums, num));\n        }\n        if(nums[l]+nums[r] == num){\n            ans = max(ans, 1+func(l+1, r-1, nums, num));\n        }\n\n        return dp[l][r] = ans;\n    }\n\n    int maxOperations(vector<int>& nums) {\n        int n = nums.size();\n        dp = vector<vector<int>>(n, vector<int>(n, -1));\n        int ans = 0;\n\n        ans = max(ans, 1+func(2, n-1, nums, nums[0]+nums[1]));\n        ans = max(ans, 1+func(0, n-3, nums, nums[n-1]+nums[n-2]));\n        ans = max(ans, 1+func(1, n-2, nums, nums[0]+nums[n-1]));\n\n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    int[][] dp;\n\n    public int maxOperations(int[] nums) {\n        int n = nums.length;\n        dp = new int[n][n];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n        int ans = 0;\n\n        ans = Math.max(ans, 1 + func(2, n - 1, nums, nums[0] + nums[1]));\n        ans = Math.max(ans, 1 + func(0, n - 3, nums, nums[n - 1] + nums[n - 2]));\n        ans = Math.max(ans, 1 + func(1, n - 2, nums, nums[0] + nums[n - 1]));\n\n        return ans;\n    }\n\n    private int func(int l, int r, int[] nums, int num) {\n        if (l >= r)\n            return 0;\n        if (dp[l][r] != -1)\n            return dp[l][r];\n\n        int ans = 0;\n        if (nums[l] + nums[l + 1] == num) {\n            ans = Math.max(ans, 1 + func(l + 2, r, nums, num));\n        }\n        if (nums[r] + nums[r - 1] == num) {\n            ans = Math.max(ans, 1 + func(l, r - 2, nums, num));\n        }\n        if (nums[l] + nums[r] == num) {\n            ans = Math.max(ans, 1 + func(l + 1, r - 1, nums, num));\n        }\n\n        return dp[l][r] = ans;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def maxOperations(self, nums: List[int]) -> int:\n        def func(l, r, nums, num):\n            if l >= r:\n                return 0\n            if dp[l][r] != -1:\n                return dp[l][r]\n\n            ans = 0\n            if nums[l] + nums[l + 1] == num:\n                ans = max(ans, 1 + func(l + 2, r, nums, num))\n            if nums[r] + nums[r - 1] == num:\n                ans = max(ans, 1 + func(l, r - 2, nums, num))\n            if nums[l] + nums[r] == num:\n                ans = max(ans, 1 + func(l + 1, r - 1, nums, num))\n\n            dp[l][r] = ans\n            return ans\n\n        n = len(nums)\n        dp = [[-1] * n for _ in range(n)]\n\n        ans = 0\n        ans = max(ans, 1 + func(2, n - 1, nums, nums[0] + nums[1]))\n        ans = max(ans, 1 + func(0, n - 3, nums, nums[-1] + nums[-2]))\n        ans = max(ans, 1 + func(1, n - 2, nums, nums[0] + nums[-1]))\n\n        return ans\n\n```
['Python', 'C++', 'Java', 'Python3']