Skip to content
MediumDpAI interview only

Maximum Total Reward Using Operations I

Asked atgoogleamazonmeta

01 · Problem

You are given an integer array rewardValues. Your total reward x starts at 0, and every index starts unmarked. You may repeat the following any number of times (including zero):

  • Choose an unmarked index i such that rewardValues[i] is strictly greater than the current x.
  • Add rewardValues[i] to x and mark index i.

Each index can be used at most once, and you may pick indices in any order. Return the maximum total reward x you can end up with.

02 · Examples

Example 01
Input
rewardValues = [2,5,3,8]
Output
15

Take 2 (x = 2), then 5 since 5 > 2 (x = 7), then 8 since 8 > 7 (x = 15). No ordering can reach more.

Example 02
Input
rewardValues = [4,4,4]
Output
4

After taking one 4, x = 4 and the remaining values are not strictly greater, so the answer is 4.

Example 03
Input
rewardValues = [1,6,4,3,2]
Output
11

Take 1 (x = 1), then 4 (x = 5), then 6 (x = 11). The final value can never reach 2 * 6 = 12.

03 · Constraints

  • 011 <= rewardValues.length <= 2000
  • 021 <= rewardValues[i] <= 2000
  • 03Each index may be chosen at most once, and a value can be added only if it is strictly greater than the current total

04 · Optimal complexity

Time
O(n * M) where M = max(rewardValues)
Space
O(M)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem