2818. Apply Operations to Maximize Score Hard

1/**
2 * [2818] Apply Operations to Maximize Score
3 *
4 * You are given an array nums of n positive integers and an integer k.
5 * Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:
6 * 
7 * 	Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously.
8 * 	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.
9 * 	Multiply your score by x.
10 * 
11 * Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.
12 * 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.
13 * Return the maximum possible score after applying at most k operations.
14 * Since the answer may be large, return it modulo 10^9 + 7.
15 *  
16 * <strong class="example">Example 1:
17 * 
18 * Input: nums = [8,3,9,3,8], k = 2
19 * Output: 81
20 * Explanation: To get a score of 81, we can apply the following operations:
21 * - 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.
22 * - 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.
23 * It can be proven that 81 is the highest score one can obtain.
24 * <strong class="example">Example 2:
25 * 
26 * Input: nums = [19,12,14,6,10,18], k = 3
27 * Output: 4788
28 * Explanation: To get a score of 4788, we can apply the following operations: 
29 * - 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.
30 * - 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.
31 * - 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.
32 * It can be proven that 4788 is the highest score one can obtain.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	1 <= nums.length == n <= 10^5
38 * 	1 <= nums[i] <= 10^5
39 * 	1 <= k <= min(n * (n + 1) / 2, 10^9)
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/apply-operations-to-maximize-score/
45// discuss: https://leetcode.com/problems/apply-operations-to-maximize-score/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn maximum_score(nums: Vec<i32>, k: i32) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_2818() {
63    }
64}
65