Maximum Amount
JP Morgan Chase● MediumINTERNOAProblem statement
There are n types of items in a shop, where the number of items of type i is denoted by quantity[i]. The price of the items is determined dynamically, where the price of the m items is equal to the remaining number of items of type i. There are m customers in line to buy the items from the shop, and each customer will buy exactly one item of any type.
The shopkeeper, being greedy, tries to sell the items in a way that maximizes revenue. Find the maximum amount the shopkeeper can earn by selling exactly one item to the customers optimally.
Function
maximumAmount(quantity: int[], m: int) → long
Complete the function maximumAmount in the editor.
maximumAmount has the following parameter:
int quantity[n]: the number of items of each type
Returns
long integer: the maximum revenue possible
Examples
Example 1
quantity = [10, 10, 8, 9, 1]m = 6return = 55
Given n = 5, quantity = [10, 80, 90, 30, 1], m = 6
One of the optimal ways to sell the items is as follows:
The maximum possible revenue is 55.
Example 2
quantity = [8, 8, 8, 8]m = 4return = 32
Here, n = 4, quantity = [8, 8, 8, 8], m = 4
The optimal way is to sell one item of each type. The total amount earned is 8 + 8 + 8 + 8 = 32.
Example 3
quantity = [1, 2, 4]m = 4return = 11
One of the optimal ways to sell the items is as follows:
Constraints
1 ≤ n ≤ 10^51 ≤ m ≤ 10^91 ≤ quantity[i] ≤ 10^9