3496. Maximize Score After Pair Deletions 🔒

Problem Description

You are given an array of integers nums. You must repeatedly perform one of the following operations while the array has more than two elements:

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

For each operation, add the sum of the removed elements to your total score.

Return the maximum possible score you can achieve.

Intuition

The problem is about removing pairs of elements from the array nums to maximize the total score, which is computed as the sum of the pairs removed. The key observation is related to how many elements remain after repeated removal operations.

Odd Number of Elements: If nums has an odd number of elements, we will eventually be left with one single element. The best scoring strategy here is to subtract the smallest element from the total sum of the array (since you want this minimum value to remain, minimizing its impact on the score).
Even Number of Elements: If nums has an even number of elements, there will be exactly two elements left after repeated operations. To maximize the score, we should ensure that the sum of the remaining two elements is minimized. This means identifying the smallest possible sum of any two consecutive elements and subtracting this from the total sum.

In essence, you want to maximize the score by cleverly minimizing the values of the elements left at the end of the operations, as these remaining elements are subtracted from the sum.

Learn more about Greedy patterns.

Solution Approach

The problem-solving approach uses a strategic reversal of our usual thinking about maximizing scores. Here's how we arrived at the solution:

Sum Calculation: First, compute the sum s of all elements in nums. This sum represents the potential maximum score before accounting for the elements that will inevitably remain after performing the operations.
Odd Length: If the length of nums is odd, the solution aims to minimize the impact of the single remaining element. To do this, the score is calculated as s - min(nums), where min(nums) is the smallest element in the array. This effectively assumes that the minimal element is the one left behind, minimizing its negative impact on the score calculation.
Even Length: If the length of nums is even, there will be two elements left, typically two consecutive ones. The task is to minimize the sum of the last two elements. Thus, the score becomes s - min(a + b for a, b in pairwise(nums)), where pairwise(nums) generates pairs of consecutive elements. By minimizing the sum of these pairs, we minimize the effect of the two elements left.

The solution leverages basic array operations like summation and finding minimum values, using them strategically based on the parity of the array's length. This systematic approach ensures that the score is maximized by carefully considering which elements remain at the end of the operations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to understand the solution approach:

Consider the array nums = [3, 1, 5, 2, 4].

Initial Step: Calculate the sum s of all elements in nums:
- Total sum ( s = 3 + 1 + 5 + 2 + 4 = 15 ).
Number of Elements: The array length is 5, which is odd.
Odd Length Handling: For odd-length arrays, we leave the smallest element behind to maximize the score:
- Find the smallest element in nums: min(nums) = 1.
Maximum Score Calculation: Subtract the smallest element from the total sum to compute the maximum score:
- Maximum score ( = s - \text{min}(nums) = 15 - 1 = 14 ).

Thus, the maximum possible score we can achieve is 14. The strategy involves leaving the smallest element behind, which minimizes the score's reduction since it stays untouched.

The logic applied here demonstrates how the solution effectively minimizes the impact of the remaining elements on the total score by strategically choosing which values to leave behind.

Solution Implementation

1from typing import List
2from itertools import pairwise
3
4class Solution:
5    def maxScore(self, nums: List[int]) -> int:
6        # Calculate the sum of all numbers in the list.
7        total_sum = sum(nums)
8
9        # Check if the length of the list is odd.
10        if len(nums) % 2 == 1:
11            # If odd, return the sum minus the minimum element in the list.
12            return total_sum - min(nums)
13
14        # If the length is even, calculate the minimum value of the sum of pairs formed by consecutive elements.
15        min_pair_sum = min(a + b for a, b in pairwise(nums))
16      
17        # Return the sum minus the minimum pair sum.
18        return total_sum - min_pair_sum
19

1class Solution {
2    public int maxScore(int[] nums) {
3        final int INF = 1 << 30; // Define a large constant for infinity
4        int n = nums.length; // Get the length of the array
5        int sum = 0, minSingle = INF; // Initialize sum and minSingle variables
6        int minPair = INF; // Initialize minPair variable
7      
8        // Loop through the array
9        for (int i = 0; i < n; ++i) {
10            sum += nums[i]; // Compute the total sum of all elements
11            minSingle = Math.min(minSingle, nums[i]); // Find the minimum single element
12
13            // Update minPair with the minimum sum of adjacent pairs, if possible
14            if (i + 1 < n) {
15                minPair = Math.min(minPair, nums[i] + nums[i + 1]);
16            }
17        }
18      
19        // If the length of the array is odd, return the sum excluding the minimum single element
20        if (n % 2 == 1) {
21            return sum - minSingle;
22        }
23      
24        // If the length of the array is even, return the sum excluding the minimum pair sum
25        return sum - minPair;
26    }
27}
28

1class Solution {
2public:
3    int maxScore(vector<int>& nums) {
4        // Define a large constant to represent infinity for comparison purposes
5        const int INF = 1 << 30;
6      
7        // Get the number of elements in the vector
8        int num_elements = nums.size();
9      
10        // Initialize variables to track the sum, minimum element, and minimum sum of two consecutive elements
11        int total_sum = 0, min_element = INF;
12        int min_consecutive_sum = INF;
13
14        // Iterate through the vector
15        for (int i = 0; i < num_elements; ++i) {
16            // Add current element to the total sum
17            total_sum += nums[i];
18          
19            // Update the minimum element if the current element is smaller
20            min_element = min(min_element, nums[i]);
21          
22            // If not at the last element, update the minimum sum of two consecutive elements
23            if (i + 1 < num_elements) {
24                min_consecutive_sum = min(min_consecutive_sum, nums[i] + nums[i + 1]);
25            }
26        }
27
28        // If the number of elements is odd, return the total sum minus the smallest element
29        if (num_elements % 2 == 1) {
30            return total_sum - min_element;
31        }
32      
33        // If the number of elements is even, return the total sum minus the smallest pair sum
34        return total_sum - min_consecutive_sum;
35    }
36};
37

1function maxScore(nums: number[]): number {
2    const inf = Infinity; // Represents a large number for comparison.
3    const n = nums.length; // Get the length of the nums array.
4    let [s, mi, t] = [0, inf, inf]; // Initialize sum (s), minimum value (mi), and temp minimum sum of two (t).
5  
6    // Loop through the array to calculate sum and determine the minimum elements.
7    for (let i = 0; i < n; ++i) {
8        s += nums[i]; // Add current element to sum.
9        mi = Math.min(mi, nums[i]); // Update minimum with the smallest value seen so far.
10      
11        // If not at the last element, find the minimum sum of adjacent pair.
12        if (i + 1 < n) {
13            t = Math.min(t, nums[i] + nums[i + 1]); // Find minimum sum of adjacent elements.
14        }
15    }
16  
17    // If the length of the array is odd, return sum minus the minimum element.
18    // If even, return sum minus the minimum adjacent pair sum.
19    return n % 2 ? s - mi : s - t;
20}
21

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the list nums. This is because the operations involved, such as sum(nums), min(nums), and iterating over pairwise(nums), each require a single pass through the list or combine in a way that can be simplified to linear complexity.

The space complexity of the code is O(1). The operations do not require extra space that scales with the input size; rather, they use a constant amount of additional space regardless of the input length.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers