We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Total Reward Using Operations I

Number: 3442

Difficulty: Medium

Paid? No

Companies: Mitsogo

Problem Description

You are given an integer array rewardValues of length n. Initially your total reward x is 0, and all indices are unmarked. You may repeatedly perform the following operation:   • Choose an unmarked index i (0 ≤ i < n).   • If rewardValues[i] is greater than your current total reward x then add rewardValues[i] to x (i.e. x = x + rewardValues[i]) and mark the index. Return the maximum total reward you can collect by performing these operations optimally.

For example, given rewardValues = [1,6,4,3,2], one optimal sequence is to mark index 0 (reward 1), then index 2 (reward 4), and finally index 1 (reward 6) so that x becomes 1 + 4 + 6 = 11.

Key Insights

  • The order of operations is completely flexible and you can choose any order.
  • When you add a reward, the rule “reward > current total” forces a chain: if you select rewards a1, a2, …, ak then they must satisfy a1 > 0, a2 > a1, a3 > (a1 + a2), and so on.
  • In other words, the rewards you choose (when sorted in the order in which they are picked) must obey a strict “prefix‐sum” condition.
  • Picking a “too small” reward early might be safe but sometimes it can “block” an even slightly larger reward later if the current total increases too much.
  • Because the condition gets stricter after each pick (the next coin must “beat” the current total) the maximum number of rewards that can be added is limited (in fact, roughly O(log(maxReward)) many picks). This lets us consider a DP whose “chain length” is small.

Space and Time Complexity

Time Complexity: O(n * L) where L is the maximum number of rewards you can pick (L is at most around 11 given the constraints)
Space Complexity: O(n * L), though by using a DP over chain length the extra space is only O(L)

Solution

The key observation is that you can choose rewards in any order as long as the “prefix‐sum” condition is met: if you have already picked rewards with total x, then you can only pick a reward v if v > x. This means the rewards you pick, when arranged in the order they were chosen (which you can assume sorted by value for analysis), must satisfy v₁ > 0, v₂ > v₁, and v₃ > (v₁ + v₂), etc.

A natural way to solve this is dynamic programming:
• Define dp[k] as the set of all totals (the sum after picking k rewards) that can be achieved by some valid sequence.
• Start with dp[0] = {0} (picking no reward yields a total of 0).
• Process each reward (sorting the rewards first is allowed since order is free) and update the dp state. For every reward r and for every k (from a maximum chain length down to 0) if some total s in dp[k] satisfies r > s then you can “append” r to that sequence, yielding a new total s + r in dp[k+1].
• At the end, the answer is the maximum total found in any of the dp[k] sets.

This method works because the maximum chain length L is very small (since each addition roughly doubles the lower bound on the next valid reward) even though n can be as large as 2000. We simply try all possibilities with at most L steps.

Code Solutions

Below are code solutions with inline comments in Python, JavaScript, C++, and Java.

# Python solution
def maximumTotalReward(rewardValues):
    # Sort the rewards in ascending order. This does not restrict the actual order of selection,
    # but helps us consider rewards from smallest to largest.
    rewardValues.sort()
    n = len(rewardValues)
    # dp[k] will be a set of possible totals after picking k rewards.
    dp = [set() for _ in range(12)]  # maximum chain length is at most 11, so we create 12 slots (including 0 picks)
    dp[0].add(0)

    for r in rewardValues:
        # Iterate backwards over chain length to avoid using the same reward twice in the same round.
        for k in range(10, -1, -1):
            for total in dp[k]:
                # If the reward is greater than the current total, it can be picked.
                if r > total:
                    dp[k+1].add(total + r)
    # The answer is the maximum total reward over all possible chain lengths.
    answer = 0
    for k in range(12):
        if dp[k]:
            answer = max(answer, max(dp[k]))
    return answer

# Example test cases
print(maximumTotalReward([1,1,3,3]))   # Output: 4
print(maximumTotalReward([1,6,4,3,2])) # Output: 11
← Back to All Questions