# LC 3180. Maximum Total Reward Using Operations I

### [Problem link](https://leetcode.com/problems/maximum-total-reward-using-operations-i/)

###### tags: `leedcode` `medium` `c++` `DP`

You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.

Initially, your total reward <code>x</code> is 0, and all indices are **unmarked** . You are allowed to perform the following operation **any** number of times:

- Choose an **unmarked** index <code>i</code> from the range <code>[0, n - 1]</code>.
- If <code>rewardValues[i]</code> is **greater** than your current total reward <code>x</code>, then add <code>rewardValues[i]</code> to <code>x</code> (i.e., <code>x = x + rewardValues[i]</code>), and **mark** the index <code>i</code>.

Return an integer denoting the **maximum ** total reward you can collect by performing the operations optimally.

**Example 1:**

<div class="example-block">
Input: <span class="example-io">rewardValues = [1,1,3,3]

Output: <span class="example-io">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:**

<div class="example-block">
Input: <span class="example-io">rewardValues = [1,6,4,3,2]

Output: <span class="example-io">11

Explanation:

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

**Constraints:**

- <code>1 <= rewardValues.length <= 2000</code>
- <code>1 <= rewardValues[i] <= 2000</code>

## Solution 1 - DP
#### C++

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        int n = rewardValues.back();
        vector<int> dp(n * 2, 0);  // dp[i][j]: 前i個rewardValues數在最大容量為j的情況下的最大容量

        for (int& val: rewardValues) {
            for (int i = 0; i < val; i++) {
                if (dp[i + val] < dp[i] + val) {
                    dp[i + val] = dp[i] + val;
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

>### Complexity
>n = sum of rewardValues
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
[0x3F](https://youtu.be/PdNYcAwsCaw)