Show problems as
Classic problem #1799HardArrayMathDynamic ProgrammingBacktrackingBit ManipulationNumber TheoryBitmask

Maximize Score After N Operations

Real-world version: Retiring Blades In Paired Sessions
Tracked in this browser only
Read Maximize Score After N Operations on LeetCode(opens in a new tab)

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

A workshop is retiring its cutting blades. There are 2 * n blades in service and values[i] is the tooth count of blade i.

The retirement happens over n sessions, numbered 1, 2, up to n. In session s the workshop picks any two blades that are still in service, takes them out of service, and banks s * g credits, where g is the greatest common divisor of the two tooth counts. After session n no blade remains in service.

The workshop chooses which two blades to retire in each session, and the session number multiplies whatever that session earns. Return the largest total credit the workshop can bank.

Examples

Example 1

Input
values = [30, 12, 25, 4]
Output
14

Retire blades 12 and 4 in session 1, whose greatest common divisor is 4, banking 1 * 4 = 4. Retire blades 30 and 25 in session 2, whose greatest common divisor is 5, banking 2 * 5 = 10. The total is 14.

Example 2

Input
values = [9, 12, 18, 4, 6, 8]
Output
43

Session 1 retires 4 and 8 for 1 * 4 = 4, session 2 retires 12 and 6 for 2 * 6 = 12, and session 3 retires 9 and 18 for 3 * 9 = 27, totalling 43.

Example 3

Input
values = [8, 8, 8, 8]
Output
24

Every pair of these blades has greatest common divisor 8, so session 1 banks 1 * 8 and session 2 banks 2 * 8, for 24 in total.

Constraints

  • 2 <= values.length <= 14
  • values.length is even, and equals 2 * n for the number of sessions n.
  • 1 <= values[i] <= 10^6
  • The largest total credit these bounds allow is 28 * 10^6.

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_retirement_credit(values: list[int]) -> int:
Java
public int bestRetirementCredit(int[] values)

More on the same topics