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 II

Number: 3443

Difficulty: Hard

Paid? No

Companies: Mitsogo

Problem Description

You are given an integer array rewardValues. Starting with a total reward x = 0 and with no index “marked”, you can repeatedly pick any unmarked index i provided that rewardValues[i] is strictly greater than your current total x. When you pick such an index, you add rewardValues[i] to your total (x = x + rewardValues[i]) and mark index i so that it cannot be picked again. Return the maximum total reward you can achieve by performing these operations optimally.

Key Insights

  • The valid operation requires that the next reward chosen must be strictly greater than the current total.
  • Any sequence of operations defines a subsequence of the rewards such that each picked reward is strictly greater than the sum of all rewards picked before.
  • Although you might be able to pick many values, if you choose “too small” a reward early on, it may limit your ability to pick larger rewards later. In other words, there is a trade‐off: a smaller valid reward makes the sum increase modestly so that you can more easily satisfy the condition for a high‐value reward later.
  • Sorting the rewards helps (since any valid sequence is in strictly increasing order), but a naive “pick the smallest possible reward” greedy strategy may not be optimal. Instead, one must choose which candidate to pick next (or to skip) using dynamic programming.
  • Given the condition a[i] > (sum of previous picks), the number of rewards that can be chosen is very limited (roughly O(log(total))), so a recursion with memoization over the current sum and an index pointer in the sorted array is efficient.

Space and Time Complexity

Time Complexity: O(n · k) in the worst case, where n is the length of rewardValues and k is the maximum number of picks (which is O(log(sum)) due to the doubling-like effect). Space Complexity: O(n · k) for the recursion stack and memoization, which in practice is efficient because k is small.

Solution

We first sort the rewards. Notice that any valid sequence of operations will pick rewards in strictly increasing order (since each reward must exceed the current total, which is the sum of all previously picked rewards, thereby forcing later picks to be larger). Thus, the problem reduces to choosing a subsequence from the sorted list such that for each picked reward r, we have r > current_total.

We then use a depth-first search (DFS) with memoization (i.e. dynamic programming) where the state is defined by (startIndex, currentTotal). For each state, we binary‐search (using the fact that the array is sorted) for the first candidate that is strictly greater than currentTotal. Then we try each candidate from that point onward, “picking” it (which increases currentTotal by the candidate’s value) and recursing over the remaining candidates. We also have the option to stop picking when no further coin can be picked, returning the current total. Finally, the answer is the maximum total reward obtained over all valid pick sequences.

Key elements of the solution:

  • Sort the rewardValues.
  • Use DFS with memoization keyed by (index, current_total) to avoid recalculations.
  • Use binary search to quickly locate the first reward greater than the current total.
  • Try all valid picks from that index onward and choose the sequence that yields the highest final total.

Code Solutions

# Python solution with detailed line-by-line comments.
from bisect import bisect_right
from functools import lru_cache

def maxTotalReward(rewardValues):
    # Sort the rewards so that any subsequence picked in order is also in increasing order.
    rewards = sorted(rewardValues)
    n = len(rewards)
    
    # Define a DFS function with memoization.
    # state: (start_index, current_sum)
    @lru_cache(maxsize=None)
    def dfs(start_index, current_sum):
        # Using binary search from start_index to find the first reward greater than current_sum.
        pos = bisect_right(rewards, current_sum, lo=start_index)
        best = current_sum  # Option of not picking any further reward.
        # Try every candidate reward from pos to end.
        for i in range(pos, n):
            # Only consider the reward if it is strictly greater than current_sum (guaranteed by bisect_right).
            candidate = rewards[i]
            # Choose the candidate and update the sum.
            new_sum = current_sum + candidate
            # Recursively compute the best total reward from the remaining rewards.
            best = max(best, dfs(i + 1, new_sum))
        return best
    
    # Start DFS from index 0 with initial sum 0.
    return dfs(0, 0)

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