Description
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 x of nums[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 10^9 + 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 <= 10^5
1 <= nums[i] <= 10^5
1 <= k <= min(n * (n + 1) / 2, 10^9)
Approach
1 Compute Prime Scores:
Calculate the prime score for each integer in the array nums. Prime score represents the number of distinct prime factors of an integer.
Initialize a boolean array prime of size upper, where upper is the maximum element in nums plus 1.
Initialize an integer array primeScore of the same size.
Set prime[0] and prime[1] to false.
Iterate over integers from 2 to upper - 1, and update primeScore and prime based on their prime factors.
2 Compute Next Greater Elements:
Initialize arrays nextGreaterElement and prevGreaterOrEqualElement of size n, where n is the length of nums.
Use a monotonic stack to find the next greater element with a greater prime score for each element in nums.
Iterate through nums and maintain a stack of indices.
For each element, pop elements from the stack if their prime score is less than or equal to the current element's prime score.
Record the index of the top of the stack as the nextGreaterElement if the stack is not empty, else set it to n.
Repeat the above process in reverse to compute prevGreaterOrEqualElement.
3 Sort and Process Elements:
Create an array of tuples (num, i) where num is the value of an element and i is its index in nums.
Sort the tuples in descending order of the first element (num).
Loop through the sorted tuples and perform the following steps:
Compute the number of operations as the minimum of (i - prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] - i) and k.
Update res by multiplying it with pow(num, operations) modulo MOD using the helper function pow.
Decrement k by the number of operations.
If k becomes 0, return res.
4 Helper Function for Exponentiation:
Implement the pow function to calculate exponentiation efficiently using modular arithmetic.
Complexity
Time complexity:
O(max(nums) * log(max(nums)) + n * log(n)). Accounting for computing prime scores, using the stack to compute next greater elements, and sorting the tuples.Space complexity:
O(max(nums) + n). Considering the space required for arrays and the stack used for computation.
Code (Swift)
class Solution {
func maximumScore(_ nums: [Int], _ k: Int) -> Int {
let MOD = 1_000_000_007
var k = k // Make a mutable copy of k
let n = nums.count
var upper = nums.max()! + 1
var prime = [Bool](repeating: true, count: upper)
prime[0] = false
prime[1] = false
var primeScore = [Int](repeating: 0, count: upper)
for i in 2..<upper {
if prime[i] {
var j = i
while j < upper {
primeScore[j] += 1
prime[j] = false
j += i
}
}
}
var nextGreaterElement = [Int](repeating: n, count: n)
var s = [Int]()
for i in (0..<n).reversed() {
while !s.isEmpty && primeScore[nums[i]] >= primeScore[nums[s.last!]] {
s.popLast()
}
nextGreaterElement[i] = s.isEmpty ? n : s.last!
s.append(i)
}
var prevGreaterOrEqualElement = [Int](repeating: -1, count: n)
s.removeAll()
for i in 0..<n {
while !s.isEmpty && primeScore[nums[i]] > primeScore[nums[s.last!]] {
s.popLast()
}
prevGreaterOrEqualElement[i] = s.isEmpty ? -1 : s.last!
s.append(i)
}
var res = 1
var tuples = [(num: Int, index: Int)]()
for i in 0..<n {
tuples.append((nums[i], i))
}
tuples.sort { a, b in
a.num > b.num
}
for (num, i) in tuples {
let operations = min(
(i - prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] - i), k)
res = (res * pow(num, operations, MOD)) % MOD
k -= operations
if k == 0 {
return res
}
}
return res
}
func pow(_ x: Int, _ n: Int, _ mod: Int) -> Int {
var res = 1
var x = x
var n = n
while n > 0 {
if n % 2 == 1 {
res = (res * x) % mod
}
x = (x * x) % mod
n /= 2
}
return res
}
}Source: Github
