Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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 <= 10^5
  • -10^4 <= nums[i] <= 10^4

Solution

Method 1 – Greedy with Sorting

Intuition

To maximize the score, always pair the largest two numbers available, as their difference will be the largest possible at each step. This greedy approach ensures the sum of differences is maximized.

Approach

  1. Sort the array in non-increasing order.
  2. Repeatedly take the first two elements, compute their difference, and add to the score.
  3. Remove these two elements and repeat until the array is empty.
  4. Return the total score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        int ans = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            ans += nums[i] - nums[i+1];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maxScore(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = nums.length - 1; i > 0; i -= 2) {
            ans += nums[i] - nums[i-1];
        }
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution:
    def maxScore(self, nums: list[int]) -> int:
        nums.sort(reverse=True)
        ans = 0
        for i in range(0, len(nums), 2):
            ans += nums[i] - nums[i+1]
        return ans

Complexity

  • ⏰ Time complexity: O(n log n) — for sorting the array.
  • 🧺 Space complexity: O(1) — only a few variables are used.