#3181
Maximum Total Reward Using Operations II
hard · 21.9% accepted · 133 likes · top 2%
array · dynamic programming · bit manipulation
Description
You are given an integer array rewardValues of length n, representing the values of rewards.
Initially, your total reward x is 0, and all indices are unmarked. You are allowed to perform the following operation any number of times:
- Choose an unmarked index i from the range [0, n - 1].
- 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 i.
Return an integer denoting the maximum total reward you can collect by performing the operations optimally.
Solution