Maximum Number of Operations With the Same Score II - Solution & Explanation

Problem Overview: You are given an integer array. Each operation removes two numbers from either the beginning or end of the array, and the sum of those two numbers becomes the operation's score. Every operation must produce the same score. The task is to maximize the number of operations you can perform.

The first operation determines the required score. After that, every pair you remove must match this sum. Because elements can only be removed from the edges, the problem naturally becomes a range decision problem over the array.

Approach 1: Two-Pointer Technique + Memoization (O(n²) time, O(n²) space)

The optimal strategy is to simulate removing elements from both ends using a two-pointer state (left, right). The first operation can produce three possible scores: nums[0] + nums[1], nums[n-2] + nums[n-1], or nums[0] + nums[n-1]. Once the target score is fixed, recursively attempt valid operations that maintain the same score. From a state (l, r), you check three options: remove the first two elements, remove the last two elements, or remove one from each side. If the pair matches the target score, move the pointers accordingly and continue.

Without caching, many subranges repeat. Using memoization or a DP table keyed by (l, r) avoids recomputation and guarantees each subproblem is solved once. This leads to O(n²) time and O(n²) space. The method relies heavily on the two-pointer technique combined with recursive decision making over the array.

Approach 2: Sliding Window + Hash Map Exploration (O(n²) time, O(n) space)

Another way to reason about the problem is to treat each possible first score as a candidate and simulate shrinking the array while maintaining that score. For a chosen score, maintain pointers at both ends and greedily test whether any of the three valid pair choices matches the score. A small hash map or counter can track previously evaluated ranges to avoid redundant work.

This approach still explores many overlapping intervals but uses lightweight bookkeeping instead of a full DP matrix. It works well for medium constraints where the recursion depth is manageable. Time complexity remains O(n²) in the worst case, while space drops closer to O(n) for tracking visited states and recursion.

Recommended for interviews: The two-pointer recursion with memoization is the expected solution. It clearly models the subproblem max operations in subarray [l, r] while enforcing a fixed score. Starting with all three possible initial scores shows you understand the constraints, and adding memoization demonstrates strong dynamic programming skills.