Recursion + cache - Java
Intuition\n Describe your first thoughts on how to solve this problem. \nTop-down recursion with a map as cache.\n# Approach\n Describe your approach to solving
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTop-down recursion with a `map` as cache.\n# Approach\n<!-- Describe your approach to solving the problem. -->\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```java []\nclass Solution {\n    public int maxOperations(int[] nums) {\n        Map<String, Integer> cache = new HashMap<>();\n        int res = 0;\n        res = Math.max(res, maxOps(nums, nums[0] + nums[1], 2, nums.length - 1, cache));\n        res = Math.max(res, maxOps(nums, nums[nums.length - 1] + nums[nums.length - 2], 0, nums.length - 3, cache));\n        res = Math.max(res, maxOps(nums, nums[0] + nums[nums.length - 1], 1, nums.length - 2, cache));\n        return res + 1;\n    }\n\n    int maxOps(int[] nums, int sum, int l, int r, Map<String, Integer> cache) {\n        if (l >= r)\n            return 0;\n        String key = sum + "-" + l + "-" + r;\n        if (cache.containsKey(key)) return cache.get(key);\n        int res = 0;\n        res = Math.max(res, sum != nums[l] + nums[r] ? 0 : 1 + maxOps(nums, sum, l + 1, r - 1, cache));\n        res = Math.max(res, sum != nums[l] + nums[l + 1] ? 0 : 1 + maxOps(nums, sum, l + 2, r, cache));\n        res = Math.max(res, sum != nums[r] + nums[r - 1] ? 0 : 1 + maxOps(nums, sum, l, r - 2, cache));\n        cache.put(key, res);\n        //System.out.println(sum + "|" + l + "|" + r + "|" + res);\n        return res;\n    }\n}\n```
['Java']