FastPrep
Problem · Greedy

Compute Maximum Earning Points

Learn this problem
● MediumAmazonINTERNOA
See Amazon hiring insights

Problem statement

To attract more customers, FastPrep Shop decides to periodically launche special promotion offers.

Recently, it introduced an offer for n items in its inventory, where the i-th item grants reward[i] reward points to the customer upon purchase. Each time a customer buys an item with an offer, they receive the corresponding reward points. However, after each purchase, the reward points of all remaining items decrease by 1, unless doing so would reduce them below 0.

Please help determine the maximum possible reward points that can be accumulated by making purchases in the most strategic and optimal way.

Note

Each item can be purchased at most once, meaning that after the i-th item is bought, its reward[i] value immediately drops to 0 and cannot be earned again. In other words, once an item is purchased, it is no longer available for future transactions.

Plz complete the function in the editor by implementing the logic to maximize the total reward points collected.

The function has a parameter called int[] deals, which represents the reward points of each item in the inventory. The function should return a long integer representing the maximum reward points that can be collected.

⋅•⋅⊰∙∘☽ 🎀 Credit to eva 🎀 ☾∘∙⊱⋅•⋅

Function

getMaxRewardPoints(deals: int[]) → long

Examples

Example 1

deals = [5, 2, 2, 3, 1]return = 7
Example 1 illustration
Considering 0-based indexing, the items can be purchased in the following order: 1. First, purchase item 2, points earned = deals[2] = 2. Points of remaining items after this purchase deals = [4, 1, 0, 2, 0]. 2. Next, purchase item 3, points earned = deals[3]= 2. Points of remaining items after this purchase deals = [3, 0, 0, 0, 0]. 3. Finally, purchase item 0, points earned = deals[0] = 3. Points of remainig items after this purchase deals = [0, 0, 0, 0, 0] At this point, no items have reward points left. The maximum earning points is 2 + 2 + 3 = 7.

Example 2

deals = [5 ,5 ,5]return = 12
Example 2 illustration
Using 0-based indexing, the items can be purchased in the following order: 1. First, purchase item 0, points earned = deals[0] = 5. Points of remaining items after this purchase deals = [0, 4, 4]. 2. Next, purchase item 1, points earned to = deals[1] = 4. and deals = [0, 0, 3]. 3. Finally, purchase item 2, points earned = deals[2] = 3 and deals = [0, 0, 0]. The maximum earning reward points is (5 + 4 + 3 = 12).

Constraints

  • 1 <= n <= 105
  • 0 < reward[i] <= 106

More Amazon problems

drafts saved locally
public long getMaxRewardPoints(int[] deals) {
  // write your code here
}
deals[5, 2, 2, 3, 1]
expected7
checking account