Show problems as
Classic problem #561EasyArrayGreedySortingCounting Sort

Array Partition

Real-world version: Doubles for the Club Regatta
Tracked in this browser only
Read Array Partition on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rowing club is drawing up doubles for a regatta. margins carries one entry per member: the number of seconds by which that member beats the club standard over the course, so a member who is slower than the standard has a negative entry. The club has an even number of members and every one of them has to be placed in exactly one double.

A double is credited with the lesser of its two members' margins, since a crew can only go as fast as its slower half. The club's score for a set of doubles is the total credited across all of them.

Return the highest score the club can reach, over every way of splitting the members into doubles.

Examples

Example 1

Input
margins = [5, 5, 1, 9]
Output
6

Rowing the doubles as (1, 5) and (5, 9) records margins of 1 and 5.

Example 2

Input
margins = [-4, -9, -2, -7]
Output
-13

Rowing (-9, -7) as one double and (-4, -2) as the other records -9 and -4.

Example 3

Input
margins = [12, -30, 7, 12, -30, 40]
Output
-11

The doubles (-30, -30), (7, 12) and (12, 40) record -30, 7 and 12.

Example 4

Input
margins = [0, -10000]
Output
-10000

Two members make up the only double, and the crew is held to the slower of them.

Constraints

  • margins.length == 2 * n
  • 1 <= n <= 10^4
  • -10^4 <= margins[i] <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_pair_total(margins: list[int]) -> int:
Java
public int bestPairTotal(int[] margins)

More on the same topics