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)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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Apply Operations to Maximize Score - Leetcode 2818 - Python • NeetCodeIO • 9,780 views views
Watch 9 more video solutions →Practice Apply Operations to Maximize Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor