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 <= 5 * 10^4
  • 1 <= rewardValues[i] <= 5 * 10^4
Similar Problems

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

This problem is a variant of the subset sum with a greedy twist: you can only add a reward if it is greater than your current total. By using a bitmask to represent which indices are marked, and dynamic programming to store the best total for each mask, we can efficiently explore all possible choices.

Approach

  1. Sort rewardValues in ascending order.
  2. Use a DP array where dp[mask] is the maximum total reward for a given set of marked indices.
  3. For each mask, try to add each unmarked index if its value is greater than the current total.
  4. Update the DP value for the new mask.
  5. Track the maximum total reward found.

Complexity

  • ⏰ Time complexity: O(n * 2^n) — Each mask and each index is considered.
  • 🧺 Space complexity: O(2^n) — For the DP array.

Code

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

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

func maxReward(rewardValues []int) int {
    n := len(rewardValues)
    sort.Ints(rewardValues)
    dp := make([]int, 1<<n)
    ans := 0
    for mask := 0; mask < 1<<n; mask++ {
        x := dp[mask]
        for i := 0; i < n; i++ {
            if mask&(1<<i) == 0 && rewardValues[i] > x {
                newMask := mask | (1 << i)
                if dp[newMask] < x+rewardValues[i] {
                    dp[newMask] = x + rewardValues[i]
                }
                if dp[newMask] > ans {
                    ans = dp[newMask]
                }
            }
        }
    }
    return ans
}
 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) {
        int n = rewardValues.length;
        Arrays.sort(rewardValues);
        int[] dp = new int[1 << n];
        int ans = 0;
        for (int mask = 0; mask < (1 << n); ++mask) {
            int x = dp[mask];
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) == 0 && rewardValues[i] > x) {
                    int newMask = mask | (1 << i);
                    dp[newMask] = Math.max(dp[newMask], x + rewardValues[i]);
                    ans = Math.max(ans, dp[newMask]);
                }
            }
        }
        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 {
        val n = rewardValues.size
        rewardValues.sort()
        val dp = IntArray(1 shl n)
        var ans = 0
        for (mask in 0 until (1 shl n)) {
            val x = dp[mask]
            for (i in 0 until n) {
                if ((mask and (1 shl i)) == 0 && rewardValues[i] > x) {
                    val newMask = mask or (1 shl i)
                    dp[newMask] = maxOf(dp[newMask], x + rewardValues[i])
                    ans = maxOf(ans, dp[newMask])
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

impl Solution {
    pub fn max_reward(reward_values: Vec<i32>) -> i32 {
        let n = reward_values.len();
        let mut vals = reward_values;
        vals.sort();
        let mut dp = vec![0; 1 << n];
        let mut ans = 0;
        for mask in 0..(1 << n) {
            let x = dp[mask];
            for i in 0..n {
                if (mask & (1 << i)) == 0 && vals[i] > x {
                    let new_mask = mask | (1 << i);
                    dp[new_mask] = dp[new_mask].max(x + vals[i]);
                    ans = ans.max(dp[new_mask]);
                }
            }
        }
        ans
    }
}
 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 {
        const n = rewardValues.length;
        rewardValues.sort((a, b) => a - b);
        const dp = Array(1 << n).fill(0);
        let ans = 0;
        for (let mask = 0; mask < (1 << n); ++mask) {
            const x = dp[mask];
            for (let i = 0; i < n; ++i) {
                if (!(mask & (1 << i)) && rewardValues[i] > x) {
                    const newMask = mask | (1 << i);
                    dp[newMask] = Math.max(dp[newMask], x + rewardValues[i]);
                    ans = Math.max(ans, dp[newMask]);
                }
            }
        }
        return ans;
    }
}