Recursive DP
Intuition\nWe can see that once we pick a sum, all operations after that must match that sum. We only have 3 initial options for the operation and so we only ha
# Intuition\nWe can see that once we pick a sum, all operations after that must match that sum. We only have 3 initial options for the operation and so we only have 3 possible sums.\n\nGiven an array and a target sum, we can test all three possibilities for the next operation and then recursively solve the remaining array after the deletions. For a particular starting sum, the inputs to the recursive call which varry are only the starting and ending points of the remaining array, so we can memoize this result in n^2 memory and time.\n\n# Approach\nCalculate the 3 possible sums and then recursively check the most operations that can be done with that particular sum.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```\nclass Solution\n{\npublic:\n\tint maxOperations(vector<int>& nums)\n\t{\n\t\tvector<vector<int>> uninitializeCache(nums.size(), vector<int>(nums.size(), -1));\n\n\t\tvector<vector<int>> cache = uninitializeCache;\n\t\tint firstTwo = nums[0] + nums[1];\n\t\tint ans = helper(nums, 0, nums.size() - 1, firstTwo, cache);\n\n\t\tcache = uninitializeCache;\n\t\tint firstAndLast = nums[0] + nums[nums.size() - 1];\n\t\tans = max(ans, helper(nums, 0, nums.size() - 1, firstAndLast, cache));\n\n\t\tcache = uninitializeCache;\n\t\tint lastTwo = nums[nums.size() - 2] + nums[nums.size() - 1];\n\t\tans = max(ans, helper(nums, 0, nums.size() - 1, lastTwo, cache));\n\n\t\treturn ans;\n\t}\n\n\tint helper(vector<int>& nums, int start, int end, int sum, vector<vector<int>>& cache)\n\t{\n\t\tif (start >= end)\n\t\t\treturn 0;\n\n\t\tint& ans = cache[start][end];\n\t\tif (ans >= 0)\n\t\t\treturn ans;\n\n\t\tint ansInt = 0;\n\t\tif (nums[start] + nums[start + 1] == sum)\n\t\t\tansInt = max(ansInt, 1 + helper(nums, start + 2, end, sum, cache));\n\n\t\tif (nums[start] + nums[end] == sum)\n\t\t\tansInt = max(ansInt, 1 + helper(nums, start + 1, end - 1, sum, cache));\n\n\t\tif (nums[end - 1] + nums[end] == sum)\n\t\t\tansInt = max(ansInt, 1 + helper(nums, start, end - 2, sum, cache));\n\n\t\tans = ansInt;\n\t\treturn ans;\n\t}\n};\n```
['C++']