Dare2Solve
Sort the Array:
nums
array in ascending order.Remove Duplicates:
Helper Function with Memoization:
helper
function that computes the maximum reward for a given num
using memoization.cache
object to store previously computed results to avoid redundant calculations.Binary Search Helper Function:
bisectLeft
function performs a binary search to find the insertion point for a given target
in a sorted array.Compute Maximum Reward:
helper
function on the largest element in the array minus one, and add the largest element in the array to this result.var maxTotalReward = function (nums) {
nums.sort((a, b) => a - b);
Sorting ensures that we process the rewards in ascending order.
var set = new Set(nums);
nums = [...set];
Converting to a set and back to an array removes duplicates, ensuring each reward is unique.
var cache = {};
Initializing a cache to store previously computed results.
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.
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.
helper
Functionfunction 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;
}
};
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.This solution is complex but optimizes the computation by removing duplicates, using binary search, and employing memoization to store intermediate results.
class Solution {
public:
int maxTotalReward(vector<int>& nums) {
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
unordered_set<int> set(nums.begin(), nums.end());
unordered_map<int, int> cache;
return nums.back() + helper(nums.back() - 1, nums, set, cache);
}
private:
int helper(int num, const vector<int>& nums, const unordered_set<int>& set, unordered_map<int, int>& 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<int>& 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;
}
};
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)
class Solution {
public int maxTotalReward(int[] nums) {
Arrays.sort(nums);
nums = removeDuplicates(nums);
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
Map<Integer, Integer> 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<Integer> set, Map<Integer, Integer> 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);
}
}
/**
* @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;
};
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
}
public class Solution {
public int MaxTotalReward(int[] nums) {
Array.Sort(nums);
nums = nums.Distinct().ToArray();
var set = new HashSet<int>(nums);
var cache = new Dictionary<int, int>();
return nums[nums.Length - 1] + Helper(nums[nums.Length - 1] - 1, nums, set, cache);
}
private int Helper(int num, int[] nums, HashSet<int> set, Dictionary<int, int> 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;
}
}
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.