Maximize Score After Pair Deletions

Problem Description

You are given an array of integers. Until the array has at most two elements, you must repeatedly delete a pair of numbers by choosing one of the following operations:

• Remove the first two elements.
• Remove the last two elements.
• Remove the first and the last element. For each removed pair, add the sum of the two removed elements to your total score. Return the maximum possible score obtainable by performing these operations optimally.

Key Insights

• Since you only remove elements from either end, the remaining elements are always contiguous in the original array.
• The total sum of all numbers is fixed; therefore, maximizing the score is equivalent to minimizing the sum of the final remaining elements.
• If the length of the array is odd, you perform operations until one element remains. Any single element can be the final one, so you want to leave the minimum element.
• If the length is even, operations stop when two elements remain. The final two elements always form a contiguous pair; thus, you want to leave the contiguous pair with the smallest sum.
• For arrays with no allowed operations (length ≤ 2), the maximum score is 0.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The key observation is that every allowed operation removes items from the ends; hence, after all operations, a contiguous block of the original array remains. Let total = sum(nums). The score accumulated is the total sum minus the sum of the remaining block.

• When n (the length of nums) is odd, the final remaining block is of length 1 and you are free to choose any element. Therefore, the best option is to leave the minimum element and get a score of total - min(nums).
• When n is even, the final remaining block is of length 2, which will be a contiguous pair in nums. In this case, you choose the adjacent pair with the minimum sum and the score is total - (minimum pair sum).

This approach reduces the search to a simple linear scan either to find the minimum element (if n is odd) or the minimum sum of any contiguous pair (if n is even). Edge cases where the length is ≤ 2 return 0 because no operation is allowed.

Code Solutions