Problem Description

You are given an array of integers called nums. You can perform operations on this array as long as it contains at least 2 elements. Each operation consists of selecting and deleting exactly 2 elements from the array in one of these three ways:

1. Delete the first two elements of nums
2. Delete the last two elements of nums
3. Delete the first and the last elements of nums

The score of each operation is the sum of the two deleted elements.

The key constraint is that all operations must have the same score. For example, if your first operation has a score of 5, then every subsequent operation must also have a score of 5.

Your task is to find the maximum number of operations you can perform while maintaining this same-score constraint.

For example, if nums = [3, 2, 1, 4, 5], you might be able to perform operations where each has a score of 5:

• Delete first and last (3 + 5 = 8) - one possible score
• Delete first two (3 + 2 = 5) - another possible score
• Delete last two (4 + 5 = 9) - yet another possible score

You need to pick one target score and maximize the number of operations with that score. The function should return the maximum possible number of operations.

Intuition

The first key observation is that once we perform the first operation, the target score s is fixed. Since we have three possible ways to perform the first operation, we only have three possible values for the target score:

• s = nums[0] + nums[1] (delete first two elements)
• s = nums[0] + nums[n-1] (delete first and last elements)
• s = nums[n-1] + nums[n-2] (delete last two elements)

Once we fix the target score s and perform the first operation, we're left with a subarray and need to find the maximum number of operations we can perform on this subarray with the same score s.

This naturally leads to a recursive approach. After removing two elements, we get a smaller array, and we face the same problem: how many operations can we perform on this smaller array with score s?

The state of our problem can be represented by the current boundaries of the array (indices i and j), and we want to find the maximum operations possible in the range [i, j] with a fixed score s.

At each step, we have up to three choices (depending on whether they give us the target score s):

1. Take the first two elements if nums[i] + nums[i+1] == s
2. Take the first and last elements if nums[i] + nums[j] == s
3. Take the last two elements if nums[j-1] + nums[j] == s

We try all valid choices and recursively solve for the remaining subarray, keeping track of the maximum operations possible.

Since we might encounter the same subarray boundaries multiple times during recursion, we use memoization to avoid redundant calculations. The @cache decorator stores the results of dfs(i, j, s) to reuse them when needed.

The final answer is 1 (for the initial operation that fixes the score) plus the maximum operations we can perform on the remaining array for each of the three possible initial scores.

Learn more about Memoization and Dynamic Programming patterns.

Solution Approach

The solution uses memoization search (dynamic programming with recursion) to efficiently explore all possible operation sequences.

Implementation Details

1. Define the recursive function dfs(i, j, s):

   • Parameters:
     • i: left boundary of the current subarray
     • j: right boundary of the current subarray (inclusive)
     • s: the target score that all operations must match
   • Returns: maximum number of operations possible in the range [i, j] with score s

2. Base case:

   • If j - i < 1, the subarray has fewer than 2 elements, so no operations are possible. Return 0.

3. Recursive cases:

   • Initialize ans = 0 to track the maximum operations
   • Option 1: Delete first two elements
     • Check if nums[i] + nums[i+1] == s
     • If valid, recursively solve for [i+2, j] and update: ans = max(ans, 1 + dfs(i+2, j, s))
   • Option 2: Delete first and last elements
     • Check if nums[i] + nums[j] == s
     • If valid, recursively solve for [i+1, j-1] and update: ans = max(ans, 1 + dfs(i+1, j-1, s))
   • Option 3: Delete last two elements
     • Check if nums[j-1] + nums[j] == s
     • If valid, recursively solve for [i, j-2] and update: ans = max(ans, 1 + dfs(i, j-2, s))

4. Memoization:

   • The @cache decorator automatically stores results of dfs(i, j, s) to avoid recomputing the same subproblems

5. Main logic:

   • Calculate the three possible initial scores:
     • s1 = nums[0] + nums[1] → After this operation, solve dfs(2, n-1, s1)
     • s2 = nums[n-1] + nums[n-2] → After this operation, solve dfs(0, n-3, s2)
     • s3 = nums[0] + nums[n-1] → After this operation, solve dfs(1, n-2, s3)
   • Return 1 + max(a, b, c) where:
     • The 1 accounts for the initial operation
     • a, b, c are the maximum operations for each initial choice

Time and Space Complexity

• Time Complexity: O(n²) for each of the three initial scores, so O(n²) overall, where n is the length of the array. Each subproblem (i, j) is computed at most once due to memoization.
• Space Complexity: O(n²) for the memoization cache storing results for all possible (i, j) pairs.

Example Walkthrough

Let's walk through the solution with nums = [3, 2, 6, 1, 4].

Step 1: Identify possible initial scores

We have three options for the first operation:

• Option 1: Delete first two (3, 2) → score = 5
• Option 2: Delete first and last (3, 4) → score = 7
• Option 3: Delete last two (1, 4) → score = 5

Step 2: Explore each initial choice

Let's trace Option 1 (score = 5):

• Initial operation: Delete (3, 2), remaining array = [6, 1, 4]
• Now we call dfs(2, 4, 5) where indices 2-4 represent [6, 1, 4]
• In this recursive call, we check:
  • Can we delete first two? 6 + 1 = 7 ≠ 5 ❌
  • Can we delete first and last? 6 + 4 = 10 ≠ 5 ❌
  • Can we delete last two? 1 + 4 = 5 ✓
• We take the last two, getting 1 + dfs(2, 2, 5)
• dfs(2, 2, 5) has only 1 element [6], so it returns 0
• Total for Option 1: 1 (initial) + 1 (recursive) = 2 operations

Let's trace Option 2 (score = 7):

• Initial operation: Delete (3, 4), remaining array = [2, 6, 1]
• Now we call dfs(1, 3, 7) where indices 1-3 represent [2, 6, 1]
• In this recursive call, we check:
  • Can we delete first two? 2 + 6 = 8 ≠ 7 ❌
  • Can we delete first and last? 2 + 1 = 3 ≠ 7 ❌
  • Can we delete last two? 6 + 1 = 7 ✓
• We take the last two, getting 1 + dfs(1, 1, 7)
• dfs(1, 1, 7) has only 1 element [2], so it returns 0
• Total for Option 2: 1 (initial) + 1 (recursive) = 2 operations

Let's trace Option 3 (score = 5):

• Initial operation: Delete (1, 4), remaining array = [3, 2, 6]
• Now we call dfs(0, 2, 5) where indices 0-2 represent [3, 2, 6]
• In this recursive call, we check:
  • Can we delete first two? 3 + 2 = 5 ✓
  • Can we delete first and last? 3 + 6 = 9 ≠ 5 ❌
  • Can we delete last two? 2 + 6 = 8 ≠ 5 ❌
• We take the first two, getting 1 + dfs(2, 2, 5)
• dfs(2, 2, 5) has only 1 element [6], so it returns 0
• Total for Option 3: 1 (initial) + 1 (recursive) = 2 operations

Step 3: Return the maximum

All three options yield 2 operations, so the answer is 2.

Note how memoization helps: if we had called dfs(2, 2, 5) multiple times (which can happen in larger examples), we'd only compute it once and reuse the cached result.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.

Time Complexity Analysis:

• The recursive function dfs(i, j, s) uses memoization with @cache decorator
• The state space is defined by parameters (i, j, s), where i and j are indices ranging from 0 to n-1
• The parameter s can only take at most 3 distinct values (corresponding to nums[0] + nums[1], nums[-1] + nums[-2], or nums[0] + nums[-1])
• For each unique combination of (i, j, s), there are O(n^2) possible states since i and j each range from 0 to n-1
• Each state is computed at most once due to memoization
• Within each recursive call, the function performs constant time operations O(1) - just comparisons and at most 3 recursive calls
• Therefore, the overall time complexity is O(n^2) * O(1) = O(n^2)

Space Complexity Analysis:

• The memoization cache stores results for all unique (i, j, s) combinations
• As analyzed above, there are O(n^2) possible states that can be cached
• The recursion depth in the worst case is O(n) when we reduce the array by 2 elements at each step
• Therefore, the space complexity is O(n^2) for the cache plus O(n) for the recursion stack, resulting in O(n^2) overall

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Considering All Three Initial Choices

Pitfall: A common mistake is to only try one or two of the possible initial operations, missing potential optimal solutions.

# WRONG: Only considering one initial choice
def maxOperations(self, nums: List[int]) -> int:
    @cache
    def dfs(left, right, target_sum):
        # ... implementation ...
  
    # Only trying the first two elements as initial operation
    return 1 + dfs(2, len(nums) - 1, nums[0] + nums[1])

Solution: Always explore all three possible initial operations since each establishes a different target sum that might lead to the maximum number of operations:

# CORRECT: Consider all three initial choices
result_left = dfs(2, n - 1, nums[0] + nums[1])
result_right = dfs(0, n - 3, nums[-1] + nums[-2])
result_ends = dfs(1, n - 2, nums[0] + nums[-1])
return 1 + max(result_left, result_right, result_ends)

2. Incorrect Index Bounds After Operations

Pitfall: Using wrong indices when updating the boundaries after an operation, especially for the "delete last two" case.

# WRONG: Incorrect boundary update for deleting last two elements
if nums[right - 1] + nums[right] == target_sum:
    max_operations = max(max_operations, 1 + dfs(left, right - 1, target_sum))  # Should be right - 2!

Solution: Carefully track index changes:

• Delete first two: [left, right] → [left + 2, right]
• Delete first and last: [left, right] → [left + 1, right - 1]
• Delete last two: [left, right] → [left, right - 2]

3. Forgetting to Add 1 for the Initial Operation

Pitfall: The recursive function dfs only counts operations after the initial one. Forgetting to add 1 for the initial operation leads to an off-by-one error.

# WRONG: Missing the initial operation count
return max(result_left, result_right, result_ends)  # Should be 1 + max(...)

Solution: Remember that each of the three branches performs one initial operation to establish the target sum, then recursively finds additional operations:

# CORRECT: Account for the initial operation
return 1 + max(result_left, result_right, result_ends)

4. Not Handling Edge Cases Properly

Pitfall: Not checking if the array has enough elements for the initial operations.

# WRONG: Accessing indices without bounds checking
def maxOperations(self, nums: List[int]) -> int:
    n = len(nums)
    # Might cause IndexError if n < 2
    result_right = dfs(0, n - 3, nums[-1] + nums[-2])  # n - 3 could be negative!

Solution: Add validation for minimum array size:

# CORRECT: Handle edge cases
def maxOperations(self, nums: List[int]) -> int:
    n = len(nums)
    if n < 2:
        return 0  # Can't perform any operations
  
    # Safe to proceed with all three initial choices
    # ...

5. Cache Invalidation Between Different Initial Choices

Pitfall: Using a global cache that doesn't account for different target sums can lead to incorrect results if not handled properly.

Solution: The provided solution correctly handles this by including the target sum s as a parameter in the memoized function dfs(i, j, s). This ensures that different target sums maintain separate cache entries, preventing conflicts between the three different initial choice branches.