You are given an array nums of n positive integers and an integer k.
Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:
nums[l, ..., r] that you haven't chosen previously.x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.x.Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.
The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.
Return the maximum possible score after applying at most k operations.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: nums = [8,3,9,3,8], k = 2 Output: 81 Explanation: To get a score of 81, we can apply the following operations: - Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9. - Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81. It can be proven that 81 is the highest score one can obtain.
Example 2:
Input: nums = [19,12,14,6,10,18], k = 3 Output: 4788 Explanation: To get a score of 4788, we can apply the following operations: - Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19. - Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342. - Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788. It can be proven that 4788 is the highest score one can obtain.
Constraints:
1 <= nums.length == n <= 1051 <= nums[i] <= 1051 <= k <= min(n * (n + 1) / 2, 109)To solve #2818 Apply Operations to Maximize Score, the key insight is that each number contributes to the final score based on how many subarrays it can dominate according to its prime score (the number of distinct prime factors). First, compute the prime score of every element using a sieve-based preprocessing technique.
Next, use a monotonic stack to determine the span of subarrays where a number remains the dominant element in terms of prime score. For each index, calculate how many subarrays it can control by finding the nearest elements with higher prime scores on both sides. This gives the total number of times the value could potentially be selected.
Finally, apply a greedy strategy: process numbers in descending order of their value and multiply them into the score as many times as allowed by their subarray count and the remaining operations. Use fast modular exponentiation to handle repeated multiplications efficiently. The approach combines stack processing and greedy selection for optimal performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prime factor preprocessing (sieve) | O(M log log M) | O(M) |
| Monotonic stack span calculation | O(n) | O(n) |
| Greedy selection with sorting | O(n log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
<div class="_1l1MA">Calculate <code>nums[i]</code>'s prime score <code>s[i]</code> by factoring in <code>O(sqrt(nums[i]))</code> time.</div>
<div class="_1l1MA">For each <code>nums[i]</code>, find the nearest index <code>left[i]</code> on the left (if any) such that <code>s[left[i]] >= s[i]</code>. if none is found, set <code>left[i]</code> to <code>-1</code>. Similarly, find the nearest index <code>right[i]</code> on the right (if any) such that <code>s[right[i]] > s[i]</code>. If none is found, set <code>right[i]</code> to <code>n</code>.</div>
<div class="_1l1MA">Use a monotonic stack to compute <code>right[i]</code> and <code>left[i]</code>.</div>
<div class="_1l1MA">For each index <code>i</code>, if <code>left[i] + 1 <= l <= i <= r <= right[i] - 1</code>, then <code>s[i]</code> is the maximum value in the range <code>[l, r]</code>. For this particular <code>i</code>, there are <code>ranges[i] = (i - left[i]) * (right[i] - i)</code> ranges where index <code>i</code> will be chosen.</div>
<div class="_1l1MA">Loop over all elements of <code>nums</code> by non-increasing prime score, each element will be chosen <code>min(ranges[i], remainingK)</code> times, where <code>reaminingK</code> denotes the number of remaining operations. Therefore, the score will be multiplied by <code>s[i]^min(ranges[i],remainingK)</code>.</div>
<div class="_1l1MA">Use fast exponentiation to quickly calculate <code>A^B mod C</code>.</div>
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Number theory is used to compute the prime score of each element, which is the count of its distinct prime factors. These scores determine which elements dominate subarrays and therefore influence how often they can contribute to the final score.
Problems like #2818 are representative of the type of advanced algorithm questions asked in FAANG-style interviews. They test multiple concepts together, including greedy thinking, monotonic stacks, and number theory optimizations.
The optimal approach combines number theory, a monotonic stack, and a greedy strategy. First compute each element's prime score, then use a monotonic stack to count how many subarrays each element dominates. Finally, greedily select the largest values and apply fast exponentiation to maximize the total score.
A monotonic stack efficiently finds the nearest elements with greater prime scores on the left and right. This helps determine the range of subarrays where a number is the dominant candidate. Using this structure reduces what would be a quadratic check to linear time.