LeetCode Problem 3496

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

LeetCode 3496 - Maximize Score After Pair Deletions

Problem Understanding

We are given an integer array nums. While the array contains more than two elements, we must repeatedly perform one of three operations:

1. Remove the first two elements.
2. Remove the last two elements.
3. Remove the first and last element.

Whenever we remove a pair, we add the sum of those two removed values to our score.

The process stops automatically when the array contains at most two elements. Our goal is to maximize the total score accumulated from all removals.

A useful way to think about the problem is that every element either contributes to the score because it gets removed, or it remains in the final array and never contributes to the score. Since every removed element contributes exactly its value once, the total score is simply:

score = sum(all elements) - sum(elements left at the end)

Therefore, maximizing the score is equivalent to minimizing the sum of the elements that remain after all operations are finished.

The constraints are important:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

The array can be very large, so any exponential or quadratic solution will be far too slow. We need an algorithm that runs in linear time.

Several edge cases are worth noting immediately:

• Arrays of length 1 already satisfy the stopping condition, so nothing can be removed.
• Arrays of length 2 also satisfy the stopping condition, so the score is 0.
• Negative numbers can appear, meaning it may be beneficial to leave very negative values behind because minimizing the remaining sum increases the score.
• Large arrays require an O(n) solution.

Problem Understanding

The problem presents an array of integers nums and asks us to perform repeated pair-deletion operations while the array has more than two elements. At each step, we can remove either the first two elements, the last two elements, or the first and last elements. Each removal adds the sum of the removed pair to a running total score. The goal is to maximize the total score by choosing the optimal sequence of pair deletions.

The input nums is a standard array of integers with length up to 10^5 and values ranging from -10^4 to 10^4. The expected output is a single integer representing the maximum possible score after performing deletions optimally.

Important points:

• If the array has three elements, exactly one operation can be applied. If it has two or fewer elements, no operation is allowed.
• Negative numbers can appear, so blindly taking any pair is not always optimal.
• Edge cases involve arrays of length 1, 2, or all negative numbers.

Approaches

Brute Force

A brute force solution would recursively try every possible operation at every step.

At each state, we have up to three choices:

• Remove the first two elements.
• Remove the last two elements.
• Remove the first and last element.

We would continue exploring all possible sequences of removals and keep the maximum score encountered.

This approach is correct because it examines every valid sequence of operations. However, the number of states grows exponentially. Even for relatively small arrays, the number of possibilities becomes enormous.

Since n can be as large as 100000, brute force is completely infeasible.

Key Observation

Instead of focusing on what gets removed, focus on what remains.

Every removed element contributes exactly once to the score. Therefore:

score = totalSum - remainingSum

So the problem becomes:

What final arrays can remain after performing the allowed operations?

Notice that every operation removes elements only from the ends. Therefore, the remaining elements always form a contiguous subarray.

If n is odd, the process must end with exactly one element.

If n is even, the process must end with exactly two elements.

The crucial observation is that every possible final contiguous segment of the required length is reachable.

• For odd n, any single element can be left behind.
• For even n, any adjacent pair can be left behind.

Therefore:

• If n is odd, we want to leave the minimum element.
• If n is even, we want to leave the adjacent pair with the minimum sum.

Once we know the minimum possible remaining sum, the answer is:

totalSum - minimumRemainingSum

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries every sequence of deletions
Optimal	O(n)	O(1)	Minimize the sum of the final remaining segment

Algorithm Walkthrough

1. Compute the sum of all elements in the array and store it in total_sum.
2. Let n be the length of the array.
3. If n is odd, the final array must contain exactly one element.

• Scan through the array and find the minimum value.
• This is the smallest possible remaining sum.
• Return total_sum - minimum_value.

4. If n is even, the final array must contain exactly two elements.

• Scan through all adjacent pairs.
• Compute nums[i] + nums[i + 1].
• Track the minimum adjacent-pair sum.
• Return total_sum - minimum_adjacent_pair_sum.

5. The returned value is the maximum achievable score.

Why it works

Every operation removes elements only from the ends, so the final remaining elements must form a contiguous segment. After all removals, the remaining segment has length:

• 1 when n is odd.
• 2 when n is even.

Every such contiguous segment is reachable through a suitable sequence of deletions. Since the score equals the total array sum minus the sum of the remaining elements, maximizing the score is exactly the same as minimizing the sum of the final remaining segment. Therefore choosing the minimum single element or minimum adjacent-pair sum yields the optimal answer. A brute-force approach would recursively explore all possible sequences of deletions. At each step, we would:

1. Consider removing the first two elements.
2. Consider removing the last two elements.
3. Consider removing the first and last elements.

Then recursively compute the maximum score for the resulting array and return the maximum among the three. While correct, this approach generates exponentially many subarrays, leading to O(3^n) time complexity, which is infeasible for n = 10^5.

Optimal Insight

The key observation is that the operations are deterministic on the endpoints. We can model the problem as a dynamic programming problem on contiguous subarrays: let dp[i][j] represent the maximum score obtainable from the subarray nums[i:j+1]. We then recursively consider the three allowed operations:

• Remove the first two elements: nums[i] + nums[i+1] + dp[i+2][j]
• Remove the last two elements: nums[j-1] + nums[j] + dp[i][j-2]
• Remove the first and last elements: nums[i] + nums[j] + dp[i+1][j-1]

Since only the ends matter, we can reduce the 2D DP to 1D using a sliding window or two-pointer approach, updating a DP array iteratively. This achieves O(n) time and space complexity by avoiding recomputation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Explores all subarrays recursively; infeasible for n=10^5
Optimal	O(n)	O(n)	Uses DP on endpoints with three possible operations

Algorithm Walkthrough

1. Initialize a DP array dp of length n where dp[i][j] represents the maximum score for subarray nums[i:j+1].
2. For subarrays of length ≤ 2, no operations can be applied, so their score is 0.
3. For subarrays of length 3, directly compute the sums of the three possible deletions.
4. For longer subarrays, compute dp[i][j] as the maximum of:

• Removing the first two elements: nums[i] + nums[i+1] + dp[i+2][j]
• Removing the last two elements: nums[j-1] + nums[j] + dp[i][j-2]
• Removing the first and last elements: nums[i] + nums[j] + dp[i+1][j-1]

5. Use memoization or a 1D DP rolling array to avoid recomputing values for overlapping subarrays.
6. Return dp[0][n-1] as the maximum possible score for the entire array.

Why it works: Each subarray’s maximum score depends only on the maximum scores of smaller subarrays obtainable by allowed deletions. By solving smaller subproblems first, we guarantee that dp[0][n-1] contains the correct maximum score. This follows the optimal substructure property of dynamic programming.

Python Solution

from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        n = len(nums)

        if n % 2 == 1:
            return total_sum - min(nums)

        min_pair_sum = float("inf")

        for i in range(n - 1):
            min_pair_sum = min(min_pair_sum, nums[i] + nums[i + 1])

        return total_sum - min_pair_sum

The implementation begins by computing the total sum of the array. This value is fixed regardless of the sequence of operations.

When the length is odd, exactly one element remains. The algorithm finds the minimum element and subtracts it from the total sum.

When the length is even, exactly two adjacent elements remain. The algorithm scans every adjacent pair and finds the minimum pair sum.

Finally, subtracting the minimum achievable remaining sum from the total array sum produces the maximum possible score. n = len(nums) if n < 3: return 0

    dp = [0] * n  # dp[i] will represent the max score for subarray starting at i
    
    # Base cases for subarrays of length 3
    for length in range(3, n + 1):
        new_dp = [0] * (n - length + 1)
        for i in range(n - length + 1):
            j = i + length - 1
            take_first_two = nums[i] + nums[i+1] + dp[i+2] if i + 2 <= j else 0
            take_last_two = nums[j-1] + nums[j] + dp[i] if i <= j-2 else 0
            take_ends = nums[i] + nums[j] + dp[i+1] if i + 1 <= j-1 else 0
            new_dp[i] = max(take_first_two, take_last_two, take_ends)
        dp = new_dp
    return dp[0]

**Implementation walkthrough:** We iterate over all subarray lengths ≥ 3. For each subarray, we compute the maximum score by evaluating the three allowed operations. `dp` stores results of smaller subarrays to avoid recomputation. The final `dp[0]` contains the answer for the entire array.

## Go Solution

```go
func maxScore(nums []int) int {
	n := len(nums)

	totalSum := 0
	for _, v := range nums {
		totalSum += v
	}

	if n%2 == 1 {
		minVal := nums[0]
		for _, v := range nums {
			if v < minVal {
				minVal = v
			}
		}
		return totalSum - minVal
	}

	minPairSum := nums[0] + nums[1]

	for i := 1; i < n-1; i++ {
		pairSum := nums[i] + nums[i+1]
		if pairSum < minPairSum {
			minPairSum = pairSum
		}
	}

	return totalSum - minPairSum
}

The Go implementation follows exactly the same logic as the Python version.

There are no special concerns regarding integer overflow because the constraints guarantee that the total sum remains comfortably within Go's int range. The solution uses simple loops and constant extra memory.

Worked Examples

Example 1

Input

nums = [2, 4, 1]

Compute the total sum:

Value	Running Sum
2	2
4	6
1	7

So:

total_sum = 7

The length is odd, so exactly one element remains.

Find the minimum element:

Element	Current Minimum
2	2
4	2
1	1

Thus:

minimum_remaining_sum = 1

Answer:

7 - 1 = 6

Output:

6

Example 2

Input

nums = [5, -1, 4, 2]

Compute total sum:

Value	Running Sum
5	5
-1	4
4	8
2	10

So:

total_sum = 10

The length is even, so exactly two adjacent elements remain.

Check every adjacent pair:

Pair	Sum
(5, -1)	4
(-1, 4)	3
(4, 2)	6

Minimum pair sum:

3

Answer:

10 - 3 = 7

Output:

7

n := len(nums)
if n < 3 {
    return 0
}

dp := make([]int, n) // dp[i] represents max score for subarray starting at i

for length := 3; length <= n; length++ {
    newDp := make([]int, n-length+1)
    for i := 0; i <= n-length; i++ {
        j := i + length - 1
        takeFirstTwo := 0
        if i+2 <= j {
            takeFirstTwo = nums[i] + nums[i+1] + dp[i+2]
        } else {
            takeFirstTwo = nums[i] + nums[i+1]
        }

        takeLastTwo := 0
        if i <= j-2 {
            takeLastTwo = nums[j-1] + nums[j] + dp[i]
        } else {
            takeLastTwo = nums[j-1] + nums[j]
        }

        takeEnds := 0
        if i+1 <= j-1 {
            takeEnds = nums[i] + nums[j] + dp[i+1]
        } else {
            takeEnds = nums[i] + nums[j]
        }

        if takeFirstTwo > takeLastTwo {
            if takeFirstTwo > takeEnds {
                newDp[i] = takeFirstTwo
            } else {
                newDp[i] = takeEnds
            }
        } else {
            if takeLastTwo > takeEnds {
                newDp[i] = takeLastTwo
            } else {
                newDp[i] = takeEnds
            }
        }
    }
    dp = newDp
}
return dp[0]

}

**Go-specific notes:** Go uses slices instead of lists. We carefully check subarray bounds to avoid out-of-range errors. `make([]int, length)` initializes slices with zeroes.

## Worked Examples

### Example 1: `[2,4,1]`

| Operation | Subarray | Score |
| --- | --- | --- |
| Remove first two | `[2,4]` → `[1]` | 2+4 = 6 |
| Remove last two | `[4,1]` → `[2]` | 4+1 = 5 |
| Remove ends | `[2,1]` → `[4]` | 2+1 = 3 |

Maximum = 6.

### Example 2: `[5,-1,4,2]`

| Operation | Subarray | Score |
| --- | --- | --- |
| Remove first two | `[5,-1]` → `[4,2]` | 5+(-1) = 4 |
| Remove last two | `[4,2]` → `[5,-1]` | 4+2 = 6 |
| Remove ends | `[5,2]` → `[-1,4]` | 5+2 = 7 |

Maximum = 7.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Single pass to compute minimum element or minimum adjacent-pair sum |
| Space | O(1) | Only a few variables are used |

The algorithm performs a constant number of linear scans over the array. No auxiliary data structures proportional to the input size are required, so the space usage remains constant.
| Time | O(n^2) | We iterate over all subarrays of length ≥ 3; each iteration evaluates three options. |
| Space | O(n) | We store DP values only for current length subarrays using rolling array. |

The complexity is quadratic in length but linear in space due to optimization.

## Test Cases

sol = Solution()

assert sol.maxScore([2, 4, 1]) == 6 # Example 1 assert sol.maxScore([5, -1, 4, 2]) == 7 # Example 2

assert sol.maxScore([5]) == 0 # Single element, nothing removed assert sol.maxScore([3, 7]) == 0 # Two elements, already finished

assert sol.maxScore([1, 2, 3]) == 5 # Leave smallest element assert sol.maxScore([-5, 1, 2]) == 3 # Negative element left behind

assert sol.maxScore([1, 2, 3, 4]) == 7 # Minimum adjacent pair is (1,2) assert sol.maxScore([10, -5, -6, 8]) == 18 # Minimum adjacent pair is (-5,-6)

assert sol.maxScore([-1, -2, -3]) == -3 # All negative values assert sol.maxScore([-1, -2, -3, -4]) == -3 # All negative, even length

assert sol.maxScore([10000] * 100000) == 999980000 # Large uniform input

## Test Summary

| Test | Why |
| --- | --- |
| `[2,4,1]` | Official odd-length example |
| `[5,-1,4,2]` | Official even-length example |
| `[5]` | Minimum array size |
| `[3,7]` | Length two, no operations possible |
| `[1,2,3]` | Basic odd-length case |
| `[-5,1,2]` | Leaving a negative value is optimal |
| `[1,2,3,4]` | Basic even-length case |
| `[10,-5,-6,8]` | Minimum adjacent pair in the middle |
| `[-1,-2,-3]` | All negative, odd length |
| `[-1,-2,-3,-4]` | All negative, even length |
| Large uniform array | Stress test for performance |

## Edge Cases

### Array of Length One

When the array contains only one element, the stopping condition is already satisfied. No operations can be performed, so the score must be zero. The formula still works because the remaining element is the entire array, making the score equal to `sum(nums) - sum(nums)`.

### Array of Length Two

A length-two array also satisfies the stopping condition immediately. No pair can be removed because the rules only allow operations while the array contains more than two elements. The implementation correctly returns zero by subtracting the sum of the only possible remaining pair from the total sum.

### Negative Numbers

Negative values can easily cause mistakes in greedy reasoning. For example, leaving a large negative value behind may increase the final score because the remaining sum becomes smaller. The solution naturally handles this by directly minimizing the remaining sum, whether the values are positive, negative, or mixed.

### Minimum Adjacent Pair Located in the Middle

For even-length arrays, the optimal remaining pair is not necessarily near either end. A naive strategy that only considers boundary elements would fail. The implementation examines every adjacent pair and therefore correctly finds the globally smallest possible remaining pair sum.

### Very Large Arrays

With up to `100000` elements, recursive search or dynamic programming over intervals would be too expensive. The linear scan approach uses `O(n)` time and `O(1)` extra space, making it efficient even at the maximum constraint limits.
# test cases
assert Solution().maxScore([2,4,1]) == 6  # example 1
assert Solution().maxScore([5,-1,4,2]) == 7  # example 2
assert Solution().maxScore([1,2]) == 0  # length < 3
assert Solution().maxScore([10,20,30]) == 50  # remove