You are given two integer arrays nums and threshold, both of length n.
Starting at step = 1, you perform the following repeatedly:
i such that threshold[i] <= step.
nums[i] to your running total.i as used and increment step by 1.Return the maximum total sum you can obtain by choosing indices optimally.
Example 1:
Input: nums = [1,10,4,2,1,6], threshold = [5,1,5,5,2,2]
Output: 17
Explanation:
step = 1, choose i = 1 since threshold[1] <= step. The total sum becomes 10. Mark index 1.step = 2, choose i = 4 since threshold[4] <= step. The total sum becomes 11. Mark index 4.step = 3, choose i = 5 since threshold[5] <= step. The total sum becomes 17. Mark index 5.step = 4, we cannot choose indices 0, 2, or 3 because their thresholds are > 4, so we end the process.Example 2:
Input: nums = [4,1,5,2,3], threshold = [3,3,2,3,3]
Output: 0
Explanation:
At step = 1 there is no index i with threshold[i] <= 1, so the process ends immediately. Thus, the total sum is 0.
Example 3:
Input: nums = [2,6,10,13], threshold = [2,1,1,1]
Output: 31
Explanation:
step = 1, choose i = 3 since threshold[3] <= step. The total sum becomes 13. Mark index 3.step = 2, choose i = 2 since threshold[2] <= step. The total sum becomes 23. Mark index 2.step = 3, choose i = 1 since threshold[1] <= step. The total sum becomes 29. Mark index 1.step = 4, choose i = 0 since threshold[0] <= step. The total sum becomes 31. Mark index 0.step = 4 all indices have been chosen, so the process ends.
Constraints:
n == nums.length == threshold.length1 <= n <= 1051 <= nums[i] <= 1091 <= threshold[i] <= nWe observe that at each step, we want to select the largest number among those that satisfy the condition to add to the total sum. Therefore, we can use a greedy approach to solve this problem.
We first sort an index array idx of length n in ascending order by their corresponding thresholds. Then, we use a sorted set or priority queue (max heap) to maintain the numbers that currently satisfy the condition. At each step, we add all numbers whose thresholds are less than or equal to the current step number into the sorted set or priority queue, and then select the largest number among them to add to the total sum. If the sorted set or priority queue is empty at this point, it means there are no numbers that satisfy the condition, and we end the process.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
Java
C++
Go
TypeScript
Rust
Practice Maximum Total Sum with Threshold Constraints with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor