#2818
Apply Operations to Maximize Score
candidate master · 1345 · lc hard +32 · verified · 53.7% accepted · 772 likes · top 45%
Description
An array nums of n positive integers and an integer k are given. Starting with a score of 1, perform up to k operations. Each operation:
- Select a non-empty subarray nums[l, ..., r] not previously selected.
- Among all elements with the highest prime score in the subarray, choose the leftmost one, call it x.
- Multiply your score by x.
The prime score of x equals the count of its distinct prime factors (e.g., 300 = 2 * 2 * 3 * 5 * 5 has prime score 3).
Return the maximum possible score 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.
Code
1
2
3