3180. Maximum Total Reward Using Operations I

Posted on Edited on In

3180. Maximum Total Reward Using Operations I

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.

Example 1:

1
2
3
4
5
6
7
Input: rewardValues = [1,1,3,3]

Output: 4

Explanation:

During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.

Example 2:

1
2
3
4
5
6
7
Input: rewardValues = [1,6,4,3,2]

Output: 11

Explanation:

Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.

Constraints:

  • 1 <= rewardValues.length <= 2000
  • 1 <= rewardValues[i] <= 2000

Hints/Notes

  • Weekly Contest 401
  • dp

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    map<int, int> m;

    int maxTotalReward(vector<int>& rewardValues) {
        set<int> s(rewardValues.begin(), rewardValues.end());
        return traverse(0, s);
    }

    int traverse(int curValue, set<int>& s) {
        if (s.lower_bound(curValue + 1) == s.end()) {
            return curValue;
        }

        if (m.contains(curValue)) {
            return m[curValue];
        }

        int res = 0;
        for (auto it = s.lower_bound(curValue + 1); it != s.end(); it++) {
            res = max(res, traverse(curValue + *it, s));
        }
        m[curValue] = res;
        return res;
    }
};