FastPrep
Problem · Heap

Maximum Amount

Learn this problem
● MediumJPMorgan ChaseINTERNOA

Problem 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:

  1. int quantity[n]: the number of items of each type

Returns

long integer: the maximum revenue possible

⸜(｡˃ ᵕ ˂ )⸝♡ Credit to chizzy_elect ᡣ𐭩ྀིྀི

Examples

Example 1

quantity = [10, 10, 8, 9, 1]m = 6return = 55
Example 1 illustration
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
Example 3 illustration
One of the optimal ways to sell the items is as follows:

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ m ≤ 10^9
  • 1 ≤ quantity[i] ≤ 10^9

    • More JPMorgan Chase problems

    drafts saved locally
    public long maximumAmount(int[] quantity, int m) {
  // write your code here
}
    quantity[10, 10, 8, 9, 1]
    m6
    expected55
    checking account