Show problems as
Classic problem #1464EasyArraySortingHeap (Priority Queue)

Maximum Product of Two Elements in an Array

Real-world version: Best Pair Of Voucher Payouts
Tracked in this browser only
Read Maximum Product of Two Elements in an Array on LeetCode(opens in a new tab)

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

A shop prints a run of vouchers. Voucher i shows the face value tokens[i], and handing it in converts to tokens[i] - 1 credits. Two vouchers may carry the same face value.

Choose two vouchers at different positions i and j. The payout for that choice is the product of their credit amounts. Return the largest payout any such choice gives.

Examples

Example 1

Input
tokens = [9, 4, 7, 1, 10]
Output
72

Taking the vouchers showing 10 and 9 gives credits of 9 and 8, and their product is 72.

Example 2

Input
tokens = [6, 6, 2]
Output
25

The two vouchers showing 6 sit at different positions, so both may be used. Each converts to 5 credits, and 5 times 5 is 25.

Example 3

Input
tokens = [1, 1000]
Output
0

Only one pair exists. The voucher showing 1 converts to 0 credits, so the payout is 0 times 999, which is 0.

Constraints

  • 2 <= tokens.length <= 500
  • 1 <= tokens[i] <= 10^3

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 max_product(tokens: list[int]) -> int:
Java
public int maxProduct(int[] tokens)

More on the same topics