Ctrl K

Growing Reward Pile

Medium
The array rewards lists the rewards lying on a table. Your pile starts at 0 points. You may take rewards one at a time in any order, each at most once. A reward of value v can be taken only if v is **strictly greater** than the current total of your pile; taking it adds v to the total. You do not have to take every reward. Return the largest total you can collect.
Example 1
rewards=[2, 5, 3, 3] → 8

Take 2 (2 > 0), then 3 (3 > 2) for a total of 5; now 5 is no longer larger than 5. A better order: 3, then 5, for a total of 8, which is the best possible.

Example 2
rewards=[4, 4, 4] → 4

The first 4 is taken; every other 4 is no longer larger than the 4 already collected.

Example 3
rewards=[1, 7, 2, 9, 4] → 17
Constraints
  • 1 ≤ len(rewards) ≤ 2000
  • 1 ≤ rewards[i] ≤ 2000
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsFewest Jumps to the End MediumMost Profitable Streak MediumReach the Last Cell MediumWarehouse Cart Routes MediumCheapest Corner-to-Corner Route Medium
loading Python…
Input
rewards=[2, 5, 3, 3]
Expected
8

Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.