操作使得分最大

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)

/*
题目思路：
1. 计算每个数的质数分数。
2. 使用Stream API对数组按质数分数排序。
3. 获取排序后前k个元素并累乘其值。
4. 为防止溢出，结果取模 10^9 + 7。
*/

import java.util.*;
import java.util.stream.*;

public class Solution {
    public static int maxScore(int[] nums, int k) {
        final int MOD = 1000000007;
        return Arrays.stream(nums)
                .boxed()
                .sorted(Comparator.comparingInt(Solution::getPrimeScore).reversed().thenComparingInt(n -> n))
                .limit(k)
                .mapToLong(Long::valueOf)
                .reduce(1, (a, b) -> (a * b) % MOD);
    }

    private static int getPrimeScore(int num) {
        Set<Integer> primeFactors = new HashSet<>();
        for (int i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                primeFactors.add(i);
                num /= i;
            }
        }
        if (num > 1) primeFactors.add(num);
        return primeFactors.size();
    }
}

本题解采用的是质数分数的贡献法结合单调栈的策略。首先，通过预处理计算每个数的质数分数（即不同质因子的数量）。使用单调栈来为每个元素找到左侧和右侧第一个质数分数更低的元素位置。这些位置帮助确定每个元素可以作为最大值的子数组的范围。对数组元素按照值进行降序排序后，尝试最多k次操作，每次选择范围最大的元素以最大化分数。通过计算该元素出现的次数（由其在单调栈中确定的左右边界计算得出），决定是否可以用完所有的操作。如果在某点用完所有操作，或者找到了最优解，循环终止。

O(n log n)

O(n)