Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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
8
9


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
Similar Problems

Solution

Method 1 – Backtracking with Memoization

Intuition

To maximize the total reward, we need to select values in an order such that each chosen value is greater than the current total. Sorting the values and using memoization allows us to efficiently explore all possible choices and avoid redundant calculations.

Approach

  1. Sort rewardValues in ascending order.
  2. Use a recursive function with memoization to try all possible choices:
    • For each unmarked index, if its value is greater than the current total, add it and recurse.
    • Track the maximum total reward found.
  3. Return the maximum total reward.

Complexity

  • ⏰ Time complexity: O(2^n) worst case, but much less in practice due to pruning and memoization.
  • 🧺 Space complexity: O(n) for recursion stack and memoization.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        unordered_set<int> memo;
        function<int(int, int)> dfs = [&](int x, int mask) {
            if (memo.count(mask)) return 0;
            memo.insert(mask);
            int ans = x;
            for (int i = 0; i < rewardValues.size(); ++i) {
                if (!(mask & (1 << i)) && rewardValues[i] > x) {
                    ans = max(ans, dfs(x + rewardValues[i], mask | (1 << i)));
                }
            }
            return ans;
        };
        return dfs(0, 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func maxReward(rewardValues []int) int {
    sort.Ints(rewardValues)
    n := len(rewardValues)
    memo := map[int]int{}
    var dfs func(x, mask int) int
    dfs = func(x, mask int) int {
        if v, ok := memo[mask]; ok { return v }
        ans := x
        for i := 0; i < n; i++ {
            if mask&(1<<i) == 0 && rewardValues[i] > x {
                ans = max(ans, dfs(x+rewardValues[i], mask|(1<<i)))
            }
        }
        memo[mask] = ans
        return ans
    }
    return dfs(0, 0)
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        int n = rewardValues.length;
        Map<Integer, Integer> memo = new HashMap<>();
        return dfs(0, 0, rewardValues, memo);
    }
    private int dfs(int x, int mask, int[] rewardValues, Map<Integer, Integer> memo) {
        if (memo.containsKey(mask)) return memo.get(mask);
        int ans = x;
        for (int i = 0; i < rewardValues.length; ++i) {
            if ((mask & (1 << i)) == 0 && rewardValues[i] > x) {
                ans = Math.max(ans, dfs(x + rewardValues[i], mask | (1 << i), rewardValues, memo));
            }
        }
        memo.put(mask, ans);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maxReward(rewardValues: IntArray): Int {
        rewardValues.sort()
        val n = rewardValues.size
        val memo = mutableMapOf<Int, Int>()
        fun dfs(x: Int, mask: Int): Int {
            if (mask in memo) return memo[mask]!!
            var ans = x
            for (i in 0 until n) {
                if (mask and (1 shl i) == 0 && rewardValues[i] > x) {
                    ans = maxOf(ans, dfs(x + rewardValues[i], mask or (1 shl i)))
                }
            }
            memo[mask] = ans
            return ans
        }
        return dfs(0, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def max_reward(reward_values: list[int]) -> int:
    reward_values.sort()
    n = len(reward_values)
    memo: dict[int, int] = {}
    def dfs(x: int, mask: int) -> int:
        if mask in memo:
            return memo[mask]
        ans = x
        for i in range(n):
            if not (mask & (1 << i)) and reward_values[i] > x:
                ans = max(ans, dfs(x + reward_values[i], mask | (1 << i)))
        memo[mask] = ans
        return ans
    return dfs(0, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn max_reward(reward_values: Vec<i32>) -> i32 {
        let mut vals = reward_values;
        vals.sort();
        let n = vals.len();
        use std::collections::HashMap;
        fn dfs(x: i32, mask: usize, vals: &Vec<i32>, memo: &mut HashMap<usize, i32>) -> i32 {
            if let Some(&v) = memo.get(&mask) { return v; }
            let mut ans = x;
            for i in 0..vals.len() {
                if (mask & (1 << i)) == 0 && vals[i] > x {
                    ans = ans.max(dfs(x + vals[i], mask | (1 << i), vals, memo));
                }
            }
            memo.insert(mask, ans);
            ans
        }
        let mut memo = HashMap::new();
        dfs(0, 0, &vals, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maxReward(rewardValues: number[]): number {
        rewardValues.sort((a, b) => a - b);
        const n = rewardValues.length;
        const memo = new Map<number, number>();
        function dfs(x: number, mask: number): number {
            if (memo.has(mask)) return memo.get(mask)!;
            let ans = x;
            for (let i = 0; i < n; ++i) {
                if (!(mask & (1 << i)) && rewardValues[i] > x) {
                    ans = Math.max(ans, dfs(x + rewardValues[i], mask | (1 << i)));
                }
            }
            memo.set(mask, ans);
            return ans;
        }
        return dfs(0, 0);
    }
}