Algorithms
Hard
2818
3001
Apply Operations to Maximize Score
apply-operations-to-maximize-score
"""
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 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 <= 105
 * 1 <= nums[i] <= 105
 * 1 <= k <= min(n * (n + 1) / 2, 109)
"""
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        
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 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 <= 105
 * 1 <= nums[i] <= 105
 * 1 <= k <= min(n * (n + 1) / 2, 109)


Please complete the code below to solve above prblem:
```python
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [8,3,9,3,8], "k": 2 }
assert my_solution.maximumScore(**test_input) == 81

test_input = { "nums": [19,12,14,6,10,18], "k": 3 }
assert my_solution.maximumScore(**test_input) == 4788

test_input = { "nums": [3289,2832,14858,22011], "k": 6 }
assert my_solution.maximumScore(**test_input) == 256720975

test_input = { "nums": [1,7,11,1,5], "k": 14 }
assert my_solution.maximumScore(**test_input) == 823751938

test_input = { "nums": [1,1,2,18,1,9,3,1], "k": 32 }
assert my_solution.maximumScore(**test_input) == 346264255

test_input = { "nums": [1,1,1], "k": 2 }
assert my_solution.maximumScore(**test_input) == 1

test_input = { "nums": [1,2,1,12,1,3], "k": 3 }
assert my_solution.maximumScore(**test_input) == 1728

test_input = { "nums": [12,5,1,6,9,1,17,14], "k": 12 }
assert my_solution.maximumScore(**test_input) == 62996359

test_input = { "nums": [1], "k": 1 }
assert my_solution.maximumScore(**test_input) == 1

test_input = { "nums": [1,10,15,1,3], "k": 13 }
assert my_solution.maximumScore(**test_input) == 499978741

test_input = { "nums": [6,1,13,10,1,17,6], "k": 27 }
assert my_solution.maximumScore(**test_input) == 630596200

test_input = { "nums": [1,14], "k": 1 }
assert my_solution.maximumScore(**test_input) == 14

test_input = { "nums": [2,1,14,5,18,1,8,5], "k": 34 }
assert my_solution.maximumScore(**test_input) == 799392504

test_input = { "nums": [5,12,11,15,10,18], "k": 18 }
assert my_solution.maximumScore(**test_input) == 557423913

test_input = { "nums": [4,1], "k": 3 }
assert my_solution.maximumScore(**test_input) == 16

test_input = { "nums": [1,2,5,1,10,1,1], "k": 20 }
assert my_solution.maximumScore(**test_input) == 600000014

test_input = { "nums": [13,16,12,15,12,1,13,1,18,1], "k": 46 }
assert my_solution.maximumScore(**test_input) == 912532739

test_input = { "nums": [10,11], "k": 3 }
assert my_solution.maximumScore(**test_input) == 1100

test_input = { "nums": [15,16,12,1,10,14], "k": 19 }
assert my_solution.maximumScore(**test_input) == 311972352

test_input = { "nums": [14,12,5,2,14], "k": 6 }
assert my_solution.maximumScore(**test_input) == 7529536

test_input = { "nums": [1,13,12,1,9,12,1,18], "k": 31 }
assert my_solution.maximumScore(**test_input) == 846374420

test_input = { "nums": [1,6,14,10,16], "k": 4 }
assert my_solution.maximumScore(**test_input) == 43904

test_input = { "nums": [14,1,9,1,10], "k": 3 }
assert my_solution.maximumScore(**test_input) == 2744

test_input = { "nums": [13,1,1,15,9,1,1], "k": 22 }
assert my_solution.maximumScore(**test_input) == 925331761

test_input = { "nums": [1,17,3,9,10,17,1,1,1,11], "k": 22 }
assert my_solution.maximumScore(**test_input) == 407065837

test_input = { "nums": [1,1,1], "k": 5 }
assert my_solution.maximumScore(**test_input) == 1

test_input = { "nums": [1,13,4,1,1], "k": 14 }
assert my_solution.maximumScore(**test_input) == 206765780

test_input = { "nums": [3,1,3,10,2,16], "k": 16 }
assert my_solution.maximumScore(**test_input) == 996976007

test_input = { "nums": [1,2,1,1,16,8,11,6], "k": 27 }
assert my_solution.maximumScore(**test_input) == 33977400

test_input = { "nums": [1,10,13,1,9,15,1], "k": 2 }
assert my_solution.maximumScore(**test_input) == 225

test_input = { "nums": [18,1], "k": 3 }
assert my_solution.maximumScore(**test_input) == 324

test_input = { "nums": [16], "k": 1 }
assert my_solution.maximumScore(**test_input) == 16

test_input = { "nums": [14,6,18,10,1,8,1,17], "k": 25 }
assert my_solution.maximumScore(**test_input) == 677968714

test_input = { "nums": [15,16,12], "k": 6 }
assert my_solution.maximumScore(**test_input) == 7776000

test_input = { "nums": [1,10,1,2], "k": 7 }
assert my_solution.maximumScore(**test_input) == 2000000

test_input = { "nums": [13,1,10,1,15,6,1,12,6], "k": 10 }
assert my_solution.maximumScore(**test_input) == 650386593

test_input = { "nums": [1,15,5,1,1,15,1,1], "k": 17 }
assert my_solution.maximumScore(**test_input) == 10486853

test_input = { "nums": [1,9], "k": 2 }
assert my_solution.maximumScore(**test_input) == 81

test_input = { "nums": [13,8,14,6,3,14,13,10,1], "k": 21 }
assert my_solution.maximumScore(**test_input) == 247566578

test_input = { "nums": [4], "k": 1 }
assert my_solution.maximumScore(**test_input) == 4

test_input = { "nums": [1,12,5,1,12], "k": 15 }
assert my_solution.maximumScore(**test_input) == 209137175

test_input = { "nums": [1,5,1,11], "k": 4 }
assert my_solution.maximumScore(**test_input) == 3025

test_input = { "nums": [3,6,17,1,1,17,18,12,16,5], "k": 9 }
assert my_solution.maximumScore(**test_input) == 359288982

test_input = { "nums": [2,2,15,2,15,15], "k": 10 }
assert my_solution.maximumScore(**test_input) == 650386593

test_input = { "nums": [1,12], "k": 1 }
assert my_solution.maximumScore(**test_input) == 12

test_input = { "nums": [2,11,1,1], "k": 2 }
assert my_solution.maximumScore(**test_input) == 121

test_input = { "nums": [11,15,18,4,11,7,1,1], "k": 32 }
assert my_solution.maximumScore(**test_input) == 179964426

test_input = { "nums": [10,1,15], "k": 1 }
assert my_solution.maximumScore(**test_input) == 15

test_input = { "nums": [10,1,1,9,14,6,4,18,8], "k": 10 }
assert my_solution.maximumScore(**test_input) == 420565606

test_input = { "nums": [6,8], "k": 3 }
assert my_solution.maximumScore(**test_input) == 288

test_input = { "nums": [13,1,10,6], "k": 4 }
assert my_solution.maximumScore(**test_input) == 16900

test_input = { "nums": [8,10,16,1,1,1], "k": 2 }
assert my_solution.maximumScore(**test_input) == 256

test_input = { "nums": [11,2,1], "k": 4 }
assert my_solution.maximumScore(**test_input) == 2662

test_input = { "nums": [15], "k": 1 }
assert my_solution.maximumScore(**test_input) == 15

test_input = { "nums": [5,5,16,12,8,1,1,7,12], "k": 34 }
assert my_solution.maximumScore(**test_input) == 15762264

test_input = { "nums": [1,1], "k": 1 }
assert my_solution.maximumScore(**test_input) == 1

test_input = { "nums": [3,18,12,8,1,3,6], "k": 23 }
assert my_solution.maximumScore(**test_input) == 18966086

test_input = { "nums": [13,1,5,6], "k": 8 }
assert my_solution.maximumScore(**test_input) == 14236560

test_input = { "nums": [1,1,15,1,9,1,1], "k": 23 }
assert my_solution.maximumScore(**test_input) == 929527145

test_input = { "nums": [6,2,1,17,9,14,1], "k": 25 }
assert my_solution.maximumScore(**test_input) == 808455901

test_input = { "nums": [1,18], "k": 3 }
assert my_solution.maximumScore(**test_input) == 324

test_input = { "nums": [1,10], "k": 2 }
assert my_solution.maximumScore(**test_input) == 100

test_input = { "nums": [17], "k": 1 }
assert my_solution.maximumScore(**test_input) == 17

test_input = { "nums": [18,13,12,1,11], "k": 8 }
assert my_solution.maximumScore(**test_input) == 537271275

test_input = { "nums": [10,14,18,6,12,14,3,13], "k": 23 }
assert my_solution.maximumScore(**test_input) == 795923147

test_input = { "nums": [16,1,14,13,3,1], "k": 6 }
assert my_solution.maximumScore(**test_input) == 9834496

test_input = { "nums": [10,4,4,3,10,1], "k": 15 }
assert my_solution.maximumScore(**test_input) == 997200007

test_input = { "nums": [2,4,1,5,14,13,13,17], "k": 19 }
assert my_solution.maximumScore(**test_input) == 241329678

test_input = { "nums": [6,1,15,1,13], "k": 12 }
assert my_solution.maximumScore(**test_input) == 820232542

test_input = { "nums": [14,13,1,14], "k": 5 }
assert my_solution.maximumScore(**test_input) == 537824

test_input = { "nums": [10,4,12,12,16,9,1,18], "k": 36 }
assert my_solution.maximumScore(**test_input) == 892891506

test_input = { "nums": [6], "k": 1 }
assert my_solution.maximumScore(**test_input) == 6

test_input = { "nums": [12], "k": 1 }
assert my_solution.maximumScore(**test_input) == 12

test_input = { "nums": [10,17,17,15,1,15,1], "k": 19 }
assert my_solution.maximumScore(**test_input) == 301460564

test_input = { "nums": [10,3,1,1,4,2,14], "k": 10 }
assert my_solution.maximumScore(**test_input) == 295359475

test_input = { "nums": [10,12], "k": 3 }
assert my_solution.maximumScore(**test_input) == 1200

test_input = { "nums": [9,10,2,3,2,1,11,1,1,13], "k": 49 }
assert my_solution.maximumScore(**test_input) == 900432644

test_input = { "nums": [1,10,18,18,3,1,8,1,15,15], "k": 18 }
assert my_solution.maximumScore(**test_input) == 38759446

test_input = { "nums": [15,1,11,13,16], "k": 14 }
assert my_solution.maximumScore(**test_input) == 753886562

test_input = { "nums": [12,1,6,1,1,4,8,17,18,1], "k": 2 }
assert my_solution.maximumScore(**test_input) == 324

test_input = { "nums": [1,1,1,17,8,18,8,1], "k": 14 }
assert my_solution.maximumScore(**test_input) == 958387476

test_input = { "nums": [7,1,6,9,11,7,13,12,1], "k": 39 }
assert my_solution.maximumScore(**test_input) == 21295572

test_input = { "nums": [12,1,1,15,2,1,1,16,1,1], "k": 8 }
assert my_solution.maximumScore(**test_input) == 294967268

test_input = { "nums": [3,14,13,1,11,1,1,1], "k": 22 }
assert my_solution.maximumScore(**test_input) == 810815174

test_input = { "nums": [14,3,6,6,1,7,13,16], "k": 28 }
assert my_solution.maximumScore(**test_input) == 312142986

test_input = { "nums": [3,4,4,15,18,12,6], "k": 8 }
assert my_solution.maximumScore(**test_input) == 428674972

test_input = { "nums": [6,15,17,9,9,17], "k": 5 }
assert my_solution.maximumScore(**test_input) == 1419857

test_input = { "nums": [2,12,1,11,12], "k": 5 }
assert my_solution.maximumScore(**test_input) == 248832

test_input = { "nums": [1,15,15], "k": 4 }
assert my_solution.maximumScore(**test_input) == 50625

test_input = { "nums": [7,11,3,1,12,10], "k": 15 }
assert my_solution.maximumScore(**test_input) == 784368200

test_input = { "nums": [18,1,11,15,16,18,18,13,10,10], "k": 41 }
assert my_solution.maximumScore(**test_input) == 911212578

test_input = { "nums": [11,15,2,14,6,15], "k": 2 }
assert my_solution.maximumScore(**test_input) == 225

test_input = { "nums": [11,2,15,1,1,11,7,1], "k": 16 }
assert my_solution.maximumScore(**test_input) == 734032462

test_input = { "nums": [1,6,12,4,10,13,7,6,17,1], "k": 50 }
assert my_solution.maximumScore(**test_input) == 377786273

test_input = { "nums": [1,5,4,18,12,1,1,1,7,12], "k": 3 }
assert my_solution.maximumScore(**test_input) == 5832

test_input = { "nums": [5,1,17,10,12], "k": 9 }
assert my_solution.maximumScore(**test_input) == 467999979

test_input = { "nums": [6,1,1,4,10,15,16,8], "k": 12 }
assert my_solution.maximumScore(**test_input) == 999939527

test_input = { "nums": [1,1], "k": 3 }
assert my_solution.maximumScore(**test_input) == 1

test_input = { "nums": [8], "k": 1 }
assert my_solution.maximumScore(**test_input) == 8

test_input = { "nums": [9,8,14,1,14,14,5,1,6], "k": 44 }
assert my_solution.maximumScore(**test_input) == 439903801