[Java/Python 3] Top-down DP: DFS cache O(n ^ 2) code w/ brief explanation and analysis.
For any given subarray of nums, there are 3 possible ways to get the score; Correspondingly we have the following 3 state transition functions:\n\n1. 1st 2 item
For any given subarray of `nums`, there are 3 possible ways to get the score; Correspondingly we have the following 3 state transition functions:\n\n1. 1st 2 items, if it sums to the score, we have recursion: `dfs(lo, hi) = 1 + dfs(lo + 2, hi)`;\n2. last 2 items, if it sums to the score, we have recursion: `dfs(lo, hi) = 1 + dfs(lo, hi - 2)`; \n3. 1st and last items, if it sums to the score, we have recursion: `dfs(lo, hi) = 1 + dfs(lo + 1, hi - 1)`;\n\nBase case: there are `1` or no items (`hi <= lo`) in subarray, we return `0`.\n\nIn addition, we need cache to avoid duplicate computations. Therefore, we can have the following code:\n\n\n\n```java\n    public int maxOperations(int[] nums) {\n        int max = 0, n = nums.length;\n        for (int score : new HashSet<>(List.of(nums[0] + nums[1], nums[0] + nums[n - 1], nums[n - 2] + nums[n - 1]))) {\n            max = Math.max(max, dfs(nums, 0, n - 1, score, new HashMap<String, Integer>()));\n        }\n        return max;\n    }\n    private int dfs(int[] nums, int lo, int hi, int score, Map<String, Integer> cache) {\n        if (hi <= lo) {\n            return 0;\n        }\n        String key = lo + ", " + hi;\n        if (!cache.containsKey(key)) {\n            int max = 0;\n            if (score == nums[lo] + nums[lo + 1]) {\n                max = Math.max(max, 1 + dfs(nums, lo + 2, hi, score, cache));\n            }\n            if (score == nums[lo] + nums[hi]) {\n                max = Math.max(max, 1 + dfs(nums, lo + 1, hi - 1, score, cache));\n            }\n            if (score == nums[hi - 1] + nums[hi]) {\n                max = Math.max(max, 1 + dfs(nums, lo, hi - 2, score, cache));\n            }\n            cache.put(key, max);\n        }\n        return cache.get(key);\n    }\n```\n\n```python\n    def maxOperations(self, nums: List[int]) -> int:\n        \n        def dfs(score: int, cache: Dict, lo = 0, hi = len(nums) - 1) -> int:\n            if hi <= lo:\n                return 0\n            if (lo, hi) not in cache:\n                max_ops1 = 1 + dfs(score, cache, lo + 2, hi) if score == sum(nums[lo : lo + 2]) else 0\n                max_ops2 = 1 + dfs(score, cache, lo, hi - 2) if score == sum(nums[hi - 1 : hi + 1]) else 0\n                max_ops3 = 1 + dfs(score, cache, lo + 1, hi - 1) if score == nums[lo] + nums[hi] else 0\n                cache[lo, hi] = max(max_ops1, max_ops2, max_ops3)\n            return cache[lo, hi]\n        \n        return max(map(dfs, \n                       set([sum(nums[: 2]), sum(nums[-2 :]), nums[0] + nums[-1]]), \n                       (defaultdict() for _ in range(3))\n                      )\n                  )\n```\nOr use built-in cache:\n```python\n    def maxOperations(self, nums: List[int]) -> int:\n        \n        @lru_cache(None)\n        def dfs(score: int, lo = 0, hi = len(nums) - 1) -> int:\n            if hi <= lo:\n                return 0\n            max_ops1 = 1 + dfs(score, lo + 2, hi) if score == sum(nums[lo : lo + 2]) else 0\n            max_ops2 = 1 + dfs(score, lo, hi - 2) if score == sum(nums[hi - 1 : hi + 1]) else 0\n            max_ops3 = 1 + dfs(score, lo + 1, hi - 1) if score == nums[lo] + nums[hi] else 0\n            return max(max_ops1, max_ops2, max_ops3)\n        \n        return max(map(dfs, set([sum(nums[: 2]), sum(nums[-2 :]), nums[0] + nums[-1]])))\n\n```\n\n\n----\n\n**Analysis:**\n\nSince the combinations of lower and upper bounds of the subarrays of `nums`, `lo`s and `hi`s, are at most `O(n ^ 2)`, where `n = nums.length`, we have\n\nTime & space: `O(n ^ 2)`.\n\n----\n\n**Q & A:**\n*Q1:* Why didn\'t you need to add score into the key. For a given low and high index, when computation repeats with different score value, you still need to ensure it\'s matching the current score value no ?\n\n*A1:* Because the `score` argument of `dfs` always matches the current `score` value. The code uses independent `dfs`s to compute max operations for different `scores`. As a result, both the `dfs` method and the `cache` vary from score to score. \n\nIn fact, the life cycle for both the `dfs` and the `cache` correspond to each `score`: when visiting a `score`, we call `dfs` and create `cache`, get the max operations for the `score`, then terminate `dfs`, and the memory corresponding to `cache` will lose reference handler (and eventually be gabage colleced by JVM) upon the termination of `dfs`. \n\nWhen visiting next `score`, the above procedure will repeat, untill all `3` different `score`s have been visited. \n\nThe max value out of the `3` `dfs`s\' results is the solution.
['Dynamic Programming', 'Depth-First Search', 'Java', 'Python3']