Choose pairings from an array to maximize the total strength contributed by each pair, where each pair’s contribution is based on the GCD of its two values.
You are given an array of positive integers. In one operation, you may choose any two unused numbers, form a pair, and earn a score equal to the operation index multiplied by the gcd of the chosen pair.
If you perform pair-formation operations, the first pair earns , the second earns , and so on up to . Every number can be used at most once.
Your task is to maximize the total score by selecting which numbers to pair and in what order to create the pairs.
Input Format
- An integer array
numsof even length. - Each element represents a positive integer available for pairing.
Output Format
Return the maximum possible total score achievable by pairing all numbers optimally.
Constraints
nums.lengthis even.- All values in
numsare positive integers. - The array size is small enough to allow state-compression search / DP over subsets.
Example 1
Input
nums = [1,2,3,4]
Output
5
Explanation
One optimal pairing order is to pair (2,4) first for 1 * gcd(2,4) = 2, then pair (1,3) for 2 * gcd(1,3) = 2. Total = 4. Another ordering can yield 5 if the better GCD pair is used later with a larger multiplier, depending on the exact pair choices. This example illustrates that pairing order matters.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.