Apply Operations to Maximize Score - Solution & Explanation
Problem Statement
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:
- Choose any non-empty subarray
nums[l, ..., r]that you haven't chosen previously. - Choose an element
xofnums[l, ..., r]with the highest prime score. If multiple such elements exist, choose the one with the smallest index. - Multiply your score by
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)
Approach Overview
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 1: Sort by Prime Score for Optimized Selection
This approach focuses on selecting elements based on their prime scores to maximize scoring efficiently. The idea is to first compute the prime score for each element in the array. We then sort the elements by these scores, and for equal scores, by their indices. Finally, we choose the top elements with the highest prime scores for up to k operations.
The solution defines a helper function to calculate the distinct prime factors of a number. Then, it prepares an array to hold the number, its prime score, and its index. After sorting with qsort based on these rules, it multiplies the first k elements by their values and returns the score modulo 10^9 + 7.
Complexity
Time Complexity: O(n log n) due to sorting and O(sqrt(m)) per number where m is the largest number (up to 10^5). Overall, this is feasible for n = 10^5.
Space Complexity: O(n) for storing elements and their properties.
Approach 2: Dynamic Programming for Subarray Optimization
This method utilizes a dynamic programming approach to iteratively build up solutions. By keeping track of subarray scores using existing results, the approach can optimize the solution selection across available operations.
This solution implements a dynamic programming approach where the dp array keeps track of maximum possible scores attainable by selecting a subarray up to a given element. The operation iteratively updates scores across operations.
Complexity
Time Complexity: O(n^2 * m^(1/2)), since iterating over each subarray results in higher complexity.
Space Complexity: O(n), due to the dp array used for storing subproblem solutions.
Approach 3: Monotonic Stack + Greedy
It is not difficult to see that the number of subarrays with the highest prime score of an element nums[i] is cnt = (i - l) times (r - i), where l is the leftmost index such that primeScore(nums[l]) \ge primeScore(nums[i]), and r is the rightmost index such that primeScore(nums[r]) \ge primeScore(nums[i]).
Since we are allowed to operate at most k times, we can greedily enumerate nums[i] from large to small, and compute the cnt of each element. If cnt \le k, then the contribution of nums[i] to the answer is nums[i]^{cnt}, and we update k = k - cnt. If cnt \gt k, then the contribution of nums[i] to the answer is nums[i]^{k}, and we break out the loop.
Return the answer after the loop. Note that the power is large, so we need to use fast power.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sort by Prime Score for Optimized Selection | Time Complexity: O(n log n) due to sorting and O(sqrt(m)) per number where m is the largest number (up to 10^5). Overall, this is feasible for n = 10^5. Space Complexity: O(n) for storing elements and their properties. |
| Dynamic Programming for Subarray Optimization | Time Complexity: O(n^2 * m^(1/2)), since iterating over each subarray results in higher complexity. Space Complexity: O(n), due to the dp array used for storing subproblem solutions. |
| Monotonic Stack + Greedy | — |
Detailed Complexity 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 |
Video Solution
Apply Operations to Maximize Score - Leetcode 2818 - Python • NeetCodeIO • 10,960 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Apply Operations to Maximize Score easy or hard?
Apply Operations to Maximize Score Python/Java solution
How to solve Apply Operations to Maximize Score in O(n log n)?
What is the best approach for Apply Operations to Maximize Score?
Is Apply Operations to Maximize Score asked at Google/Amazon/Meta?
What data structure is used in Apply Operations to Maximize Score?
What is the time complexity of Apply Operations to Maximize Score?
Ready to solve this problem?
Practice Apply Operations to Maximize Score with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor