Skip to content

3496. Maximize Score After Pair Deletions πŸ”’

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.

 

Example 1:

Input: nums = [2,4,1]

Output: 6

Explanation:

The possible operations are:

  • Remove the first two elements (2 + 4) = 6. The remaining array is [1].
  • Remove the last two elements (4 + 1) = 5. The remaining array is [2].
  • Remove the first and last elements (2 + 1) = 3. The remaining array is [4].

The maximum score is obtained by removing the first two elements, resulting in a final score of 6.

Example 2:

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

Output: 7

Explanation:

The possible operations are:

  • Remove the first and last elements (5 + 2) = 7. The remaining array is [-1, 4].
  • Remove the first two elements (5 + -1) = 4. The remaining array is [4, 2].
  • Remove the last two elements (4 + 2) = 6. The remaining array is [5, -1].

The maximum score is obtained by removing the first and last elements, resulting in a total score of 7.

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Solutions

Solution 1: Reverse Thinking

According to the problem description, each operation removes the two elements at the endpoints. Therefore, when the number of elements is odd, one element will eventually remain; when the number of elements is even, two consecutive elements in the array will eventually remain.

To maximize the score after deletions, we should minimize the remaining elements.

Thus, if the array \(\textit{nums}\) has an odd number of elements, the answer is the sum of all elements \(s\) in the array \(\textit{nums}\) minus the minimum value \(\textit{mi}\) in \(\textit{nums}\); if the array \(\textit{nums}\) has an even number of elements, the answer is the sum of all elements \(s\) in the array \(\textit{nums}\) minus the minimum sum of any two consecutive elements.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def maxScore(self, nums: List[int]) -> int:
        s = sum(nums)
        if len(nums) & 1:
            return s - min(nums)
        return s - min(a + b for a, b in pairwise(nums))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxScore(int[] nums) {
        final int inf = 1 << 30;
        int n = nums.length;
        int s = 0, mi = inf;
        int t = inf;
        for (int i = 0; i < n; ++i) {
            s += nums[i];
            mi = Math.min(mi, nums[i]);
            if (i + 1 < n) {
                t = Math.min(t, nums[i] + nums[i + 1]);
            }
        }
        if (n % 2 == 1) {
            return s - mi;
        }
        return s - t;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxScore(vector<int>& nums) {
        const int inf = 1 << 30;
        int n = nums.size();
        int s = 0, mi = inf;
        int t = inf;
        for (int i = 0; i < n; ++i) {
            s += nums[i];
            mi = min(mi, nums[i]);
            if (i + 1 < n) {
                t = min(t, nums[i] + nums[i + 1]);
            }
        }
        if (n % 2 == 1) {
            return s - mi;
        }
        return s - t;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maxScore(nums []int) int {
    const inf = 1 << 30
    n := len(nums)
    s, mi, t := 0, inf, inf
    for i, x := range nums {
        s += x
        mi = min(mi, x)
        if i+1 < n {
            t = min(t, x+nums[i+1])
        }
    }
    if n%2 == 1 {
        return s - mi
    }
    return s - t
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maxScore(nums: number[]): number {
    const inf = Infinity;
    const n = nums.length;
    let [s, mi, t] = [0, inf, inf];
    for (let i = 0; i < n; ++i) {
        s += nums[i];
        mi = Math.min(mi, nums[i]);
        if (i + 1 < n) {
            t = Math.min(t, nums[i] + nums[i + 1]);
        }
    }
    return n % 2 ? s - mi : s - t;
}

Comments