
Intuition
- Sort and Deduplicate: - Sort the rewards array and remove duplicates for easier processing.
- Memoization and Recursion: - Utilize memoization to avoid redundant computations in a recursive function.
- Binary Search: - Implement binary search to efficiently find insertion points.
- Main Computation: - Compute the maximum reward by recursively exploring all possible combinations.
- Base Case: - Return rewards that are already included or are zero.
- Return Result: - Return the maximum total reward achieved.
Approach
- Sort the Array:
- The first step is to sort the
nums
array in ascending order. - Remove Duplicates: - Convert the sorted array into a set to remove duplicates and then back into an array.
- Helper Function with Memoization:
- Define a recursive
helper
function that computes the maximum reward for a givennum
using memoization. - Use acache
object to store previously computed results to avoid redundant calculations. - Binary Search Helper Function:
- The
bisectLeft
function performs a binary search to find the insertion point for a giventarget
in a sorted array. - Compute Maximum Reward:
- Start the computation by calling the
helper
function on the largest element in the array minus one, and add the largest element in the array to this result.
Detailed Explanation
JavaScript Code
Sort the Array
var maxTotalReward = function (nums) {
nums.sort((a, b) => a - b);
Sorting ensures that we process the rewards in ascending order.
Remove Duplicates
var set = new Set(nums);
nums = [...set];
Converting to a set and back to an array removes duplicates, ensuring each reward is unique.
Helper Function with Memoization
var cache = {};
Initializing a cache to store previously computed results.
Binary Search Helper Function
var bisectLeft = function (arr, target) {
var lo = 0;
var hi = arr.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
};
The bisectLeft
function finds the insertion point for a target value in a sorted array using binary search.
Compute Maximum Reward
return nums[nums.length - 1] + helper(nums[nums.length - 1] - 1);
The main computation starts with the largest reward minus one and adds the largest reward to the result of the recursive helper
function.
Recursive `helper` Function
function helper(num) {
if (num in cache) return cache[num];
if (set.has(num) || num === 0) return num;
var ind = bisectLeft(nums, num);
var res = 0;
for (var i = 0; i < ind; i++) {
res = Math.max(
res,
nums[i] + helper(Math.min(nums[i] - 1, num - nums[i]))
);
}
cache[num] = res;
return res;
}
};
- Base Case: If the number is in the set or zero, return the number.
- Binary Search: Find the insertion point for the current number.
- Recursion and Memoization: Recursively compute the maximum reward, using memoization to store results and avoid redundant calculations.
Complexity
- Time Complexity: O(n log n)
- Sorting the array takes O(n log n).
- Removing duplicates using a Set takes O(n).
- The recursive
helper
function could potentially explore many subproblems, leading to a complexity of O(n^2) in the worst case, considering the binary search and recursive calls. - Space Complexity: O(n) - The cache and set use additional space proportional to the number of unique elements in the array.
This solution is complex but optimizes the computation by removing duplicates, using binary search, and employing memoization to store intermediate results.
Code
C++
class Solution {
public:
int maxTotalReward(vector& nums) {
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
unordered_set set(nums.begin(), nums.end());
unordered_map cache;
return nums.back() + helper(nums.back() - 1, nums, set, cache);
}
private:
int helper(int num, const vector& nums, const unordered_set& set, unordered_map& cache) {
if (cache.find(num) != cache.end()) {
return cache[num];
}
if (set.find(num) != set.end() || num == 0) {
return num;
}
int ind = bisectLeft(nums, num);
int res = 0;
for (int i = 0; i < ind; ++i) {
res = max(res, nums[i] + helper(min(nums[i] - 1, num - nums[i]), nums, set, cache));
}
cache[num] = res;
return res;
}
int bisectLeft(const vector& arr, int target) {
int lo = 0;
int hi = arr.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
};
Python
class Solution:
def maxTotalReward(self, nums: List[int]) -> int:
nums.sort()
nums = list(set(nums))
nums.sort()
cache = {}
set_nums = set(nums)
def helper(num: int) -> int:
if num in cache:
return cache[num]
if num in set_nums or num == 0:
return num
ind = bisect_left(nums, num)
res = 0
for i in range(ind):
res = max(res, nums[i] + helper(min(nums[i] - 1, num - nums[i])))
cache[num] = res
return res
return nums[-1] + helper(nums[-1] - 1)
Java
class Solution {
public int maxTotalReward(int[] nums) {
Arrays.sort(nums);
nums = removeDuplicates(nums);
Set set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
Map cache = new HashMap<>();
return nums[nums.length - 1] + helper(nums[nums.length - 1] - 1, nums, set, cache);
}
private int helper(int num, int[] nums, Set set, Map cache) {
if (cache.containsKey(num)) {
return cache.get(num);
}
if (set.contains(num) || num == 0) {
return num;
}
int ind = bisectLeft(nums, num);
int res = 0;
for (int i = 0; i < ind; i++) {
res = Math.max(res, nums[i] + helper(Math.min(nums[i] - 1, num - nums[i]), nums, set, cache));
}
cache.put(num, res);
return res;
}
private int bisectLeft(int[] arr, int target) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
private int[] removeDuplicates(int[] nums) {
if (nums.length == 0) {
return nums;
}
int[] temp = new int[nums.length];
int j = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] != nums[i + 1]) {
temp[j++] = nums[i];
}
}
temp[j++] = nums[nums.length - 1];
return Arrays.copyOfRange(temp, 0, j);
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var maxTotalReward = function (nums) {
nums.sort((a, b) => a - b);
var set = new Set(nums);
nums = [...set];
var cache = {};
return nums[nums.length - 1] + helper(nums[nums.length - 1] - 1);
function helper(num) {
if (num in cache) return cache[num];
if (set.has(num) || num === 0) return num;
var ind = bisectLeft(nums, num);
var res = 0;
for (var i = 0; i < ind; i++) {
res = Math.max(
res,
nums[i] + helper(Math.min(nums[i] - 1, num - nums[i]))
);
}
cache[num] = res;
return res;
}
};
/**
* @param {number[]} arr
* @param {number} target
* @returns {number}
*/
var bisectLeft = function (arr, target) {
var lo = 0;
var hi = arr.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
};
Go
func maxTotalReward(nums []int) int {
sort.Ints(nums)
nums = removeDuplicates(nums)
set := make(map[int]struct{})
for _, num := range nums {
set[num] = struct{}{}
}
cache := make(map[int]int)
return nums[len(nums)-1] + helper(nums[len(nums)-1]-1, nums, set, cache)
}
func helper(num int, nums []int, set map[int]struct{}, cache map[int]int) int {
if val, found := cache[num]; found {
return val
}
if _, found := set[num]; found || num == 0 {
return num
}
ind := bisectLeft(nums, num)
res := 0
for i := 0; i < ind; i++ {
res = max(res, nums[i]+helper(min(nums[i]-1, num-nums[i]), nums, set, cache))
}
cache[num] = res
return res
}
func bisectLeft(arr []int, target int) int {
lo := 0
hi := len(arr)
for lo < hi {
mid := (lo + hi) / 2
if arr[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
func removeDuplicates(nums []int) []int {
if len(nums) == 0 {
return nums
}
res := []int{nums[0]}
for i := 1; i < len(nums); i++ {
if nums[i] != nums[i-1] {
res = append(res, nums[i])
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
C#
public class Solution {
public int MaxTotalReward(int[] nums) {
Array.Sort(nums);
nums = nums.Distinct().ToArray();
var set = new HashSet(nums);
var cache = new Dictionary();
return nums[nums.Length - 1] + Helper(nums[nums.Length - 1] - 1, nums, set, cache);
}
private int Helper(int num, int[] nums, HashSet set, Dictionary cache) {
if (cache.ContainsKey(num)) {
return cache[num];
}
if (set.Contains(num) || num == 0) {
return num;
}
int ind = BisectLeft(nums, num);
int res = 0;
for (int i = 0; i < ind; i++) {
res = Math.Max(res, nums[i] + Helper(Math.Min(nums[i] - 1, num - nums[i]), nums, set, cache));
}
cache[num] = res;
return res;
}
private int BisectLeft(int[] arr, int target) {
int lo = 0, hi = arr.Length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
}
Conclusion
In this problem, we aimed to maximize the total reward by efficiently selecting rewards from a given array. We employed sorting and deduplication to simplify processing, utilized memoization to avoid redundant computations, and implemented binary search for efficient insertion point identification. Through recursive exploration of all possible combinations and careful handling of base cases, we determined the maximum achievable total reward. This solution optimally navigates the given constraints to achieve the desired outcome.