Watch 10 video solutions for Apply Operations to Maximize Score, a hard level problem involving Array, Math, Stack. This walkthrough by NeetCodeIO has 10,822 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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)Problem Overview: You are given an array and can perform up to k operations. In each operation, you select a subarray and multiply the result by the element with the highest prime score (number of distinct prime factors). The goal is to maximize the final product modulo 1e9+7.
Approach 1: Dynamic Programming for Subarray Optimization (O(n^2) time, O(n) space)
This approach explicitly evaluates subarrays and keeps track of the best score contribution for each possible operation. You compute the prime score for every element, then iterate through possible subarray ranges while updating the maximum achievable product. A DP array tracks optimal results after selecting subarrays up to a given index. While conceptually straightforward, the nested iteration over subarrays makes this approach expensive for large inputs.
Approach 2: Sort by Prime Score for Optimized Selection (O(n log n) time, O(n) space)
The optimal solution relies on a greedy strategy combined with a monotonic stack. First compute the prime score (number of distinct prime factors) for each value using a number theory factorization method. Then determine how many subarrays treat each element as the dominant prime score using a stack to find the previous and next greater prime score indices. This gives the number of subarrays where the element contributes to the score.
Next, sort elements by value in descending order. For each element, determine how many times it can be used based on its subarray contribution and remaining k. Multiply the result by value^count using fast modular exponentiation. This greedy selection ensures the largest values contribute first, maximizing the product.
Recommended for interviews: Interviewers expect the greedy solution with a monotonic stack. The DP approach demonstrates understanding of the problem space, but the optimized method shows stronger algorithmic skill by combining array processing, stack-based span calculation, and prime factor analysis.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming for Subarray Optimization | O(n^2) | O(n) | Useful for reasoning about subarray contributions or when constraints are small |
| Greedy with Prime Score + Monotonic Stack | O(n log n) | O(n) | Optimal approach for large arrays; calculates contribution spans and prioritizes largest values |