Problem

Example 1:

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.