3181. Maximum Total Reward Using Operations II

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

1. Sort the Array: - The first step is to sort the nums array in ascending order.
2. Remove Duplicates: - Convert the sorted array into a set to remove duplicates and then back into an array.
3. Helper Function with Memoization: - Define a recursive helper function that computes the maximum reward for a given num using memoization. - Use a cache object to store previously computed results to avoid redundant calculations.
4. Binary Search Helper Function: - The bisectLeft function performs a binary search to find the insertion point for a given target in a sorted array.
5. 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.