DP | Memorization | easy to understand | readable | beats 99%
Intuition\n\n\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the maximum number of operations that can be performed
# Intuition\n\n\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the maximum number of operations that can be performed on an array of integers, such that each operation yields the same score. The operations involve selecting pairs of elements from either end or both ends of the array and summing them up.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Dynamic Programming with Memoization: We can solve this problem efficiently using dynamic programming with memoization. We define a recursive function that explores all possible choices of pairs of elements, keeping track of the maximum number of operations for each choice.\n\n- Recurrence Relation: The recurrence relation for our function considers three cases: selecting the first two elements, selecting the first and last elements, and selecting the last two elements. We compute the maximum number of operations possible for each case and choose the maximum among them.\n\n- Memoization: We use a 2D memoization array to store the results of subproblems. Before computing the maximum operations for a particular subarray, we check if it has already been computed. If so, we retrieve the result from the memoization table instead of recomputing it.\n\n- Base Cases: We handle base cases where the subarray has only one or no elements. In such cases, the maximum number of operations possible is zero.\n\n- Main Function: In the main function, we initialize the memoization array and call the recursive function with appropriate parameters for each of the three cases: selecting the first two elements, selecting the first and last elements, and selecting the last two elements. Finally, we return the maximum number of operations among these three cases.\n# why using only one dp table isn\'t three dp table is reqired for three case\n\nUsing only one dynamic programming (DP) table suffices because the paths corresponding to different previous sum values never collide within the DP table. At any given point where paths might intersect, only one path can pass through, and it will correspond to a specific previous sum value. Consequently, the calculated answer at that point is only relevant for future paths with the same previous sum value. Therefore, a single DP table effectively stores the results for all cases, ensuring accurate memoization and preventing interference between different cases.\nbecause of this one dp table is suffice\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this approach is O(n^2), where n is the number of elements in the input array. This is because the memoization table has dimensions of n * n, and each entry in the table is computed once.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is also O(n^2) due to the memoization table, which stores the results of subproblems. Additionally, the recursive stack can go up to O(n) levels in the worst case. Therefore, the total space complexity is dominated by the memoization table.\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int findMaxOpsHelper(std::vector<int>& nums, int left, int right, int previousSum, std::vector<std::vector<int>>& memoization) {\n        if (left >= right)\n            return 0;\n        if (memoization[left][right] != 0)\n            return memoization[left][right];\n\n        int maxOps = 0;\n        if (nums[left] + nums[left + 1] == previousSum)\n            maxOps = std::max(maxOps, findMaxOpsHelper(nums, left + 2, right, previousSum, memoization) + 1);\n        if (nums[left] + nums[right] == previousSum)\n            maxOps = std::max(maxOps, findMaxOpsHelper(nums, left + 1, right - 1, previousSum, memoization) + 1);\n        if (nums[right] + nums[right - 1] == previousSum)\n            maxOps = std::max(maxOps, findMaxOpsHelper(nums, left, right - 2, previousSum, memoization) + 1);\n\n        return memoization[left][right] = maxOps;\n    }\npublic:\n    int maxOperations(vector<int>& nums) {\n        int maxOperations = 0;\n        int len = nums.size();\n        std::vector<std::vector<int>> memoization(len, std::vector<int>(len, 0));\n        int start = 0;\n        int end = len - 1;\n\n        maxOperations = std::max(maxOperations,\n                findMaxOpsHelper(nums, start + 2, end, nums[start] + nums[start + 1], memoization) + 1);\n        maxOperations = std::max(maxOperations,\n                findMaxOpsHelper(nums, start + 1, end - 1, nums[start] + nums[end], memoization) + 1);\n        maxOperations = std::max(maxOperations,\n                findMaxOpsHelper(nums, start, end - 2, nums[end] + nums[end - 1], memoization) + 1);\n\n        return maxOperations;\n    }\n};\n```\n```java []\nclass Solution {\n    public int maxOperations(int[] nums) {\n        int maxOperations = 0;\n        int len = nums.length;\n        int[][] memoization = new int[len][len];\n        int start = 0;\n        int end = len - 1;\n\n        maxOperations = Math.max(maxOperations,\n                findMaxOpsHelper(nums, start + 2, end, nums[start] + nums[start + 1], memoization) + 1);\n        maxOperations = Math.max(maxOperations,\n                findMaxOpsHelper(nums, start + 1, end - 1, nums[start] + nums[end], memoization) + 1);\n        maxOperations = Math.max(maxOperations,\n                findMaxOpsHelper(nums, start, end - 2, nums[end] + nums[end - 1], memoization) + 1);\n\n        return maxOperations;\n    }\n\n    private int findMaxOpsHelper(int[] nums, int left, int right, int previousSum, int[][] memoization) {\n        if (left >= right)\n            return 0;\n        if (memoization[left][right] != 0)\n            return memoization[left][right];\n\n        int maxOps = 0;\n        if (nums[left] + nums[left + 1] == previousSum)\n            maxOps = Math.max(maxOps, findMaxOpsHelper(nums, left + 2, right, previousSum, memoization) + 1);\n        if (nums[left] + nums[right] == previousSum)\n            maxOps = Math.max(maxOps, findMaxOpsHelper(nums, left + 1, right - 1, previousSum, memoization) + 1);\n        if (nums[right] + nums[right - 1] == previousSum)\n            maxOps = Math.max(maxOps, findMaxOpsHelper(nums, left, right - 2, previousSum, memoization) + 1);\n\n        return memoization[left][right] = maxOps;\n    }\n}\n  \n```\n```python []\nclass Solution:\n    def maxOperations(self, nums: List[int]) -> int:\n        maxOperations = 0\n        length = len(nums)\n        memoization = [[0] * length for _ in range(length)]\n        start = 0\n        end = length - 1\n\n        maxOperations = max(maxOperations, self.findMaxOpsHelper(nums, start + 2, end, nums[start] + nums[start + 1], memoization) + 1)\n        maxOperations = max(maxOperations, self.findMaxOpsHelper(nums, start + 1, end - 1, nums[start] + nums[end], memoization) + 1)\n        maxOperations = max(maxOperations, self.findMaxOpsHelper(nums, start, end - 2, nums[end] + nums[end - 1], memoization) + 1)\n\n        return maxOperations\n\n    def findMaxOpsHelper(self, nums: List[int], left: int, right: int, previousSum: int, memoization: List[List[int]]) -> int:\n        if left >= right:\n            return 0\n        if memoization[left][right] != 0:\n            return memoization[left][right]\n\n        maxOps = 0\n        if nums[left] + nums[left + 1] == previousSum:\n            maxOps = max(maxOps, self.findMaxOpsHelper(nums, left + 2, right, previousSum, memoization) + 1)\n        if nums[left] + nums[right] == previousSum:\n            maxOps = max(maxOps, self.findMaxOpsHelper(nums, left + 1, right - 1, previousSum, memoization) + 1)\n        if nums[right] + nums[right - 1] == previousSum:\n            maxOps = max(maxOps, self.findMaxOpsHelper(nums, left, right - 2, previousSum, memoization) + 1)\n\n        memoization[left][right] = maxOps\n        return maxOps\n\n```
['Dynamic Programming', 'Recursion', 'Python', 'C++', 'Java', 'Python3']