# Apply Operations to Maximize Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/apply-operations-to-maximize-score)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-maximize-score
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Monotonic Stack
---
## Problem
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)`

# Approaches
## Brute Force Calculation of Contribution Count
This approach revolves around a key insight: the problem can be broken down into determining, for each element `nums[i]`, the total number of subarrays where it would be the chosen element. Once we have this count for every element, the problem becomes a greedy selection task. To maximize the product, we should multiply by the largest numbers as many times as possible. The number of times we can use `nums[i]` is precisely the number of subarrays where it's the 'best' element according to the problem's rules.

This specific version of the approach calculates these counts using a straightforward, but inefficient, brute-force method.
**Time:** O(n^2 + M log log M), where n is the length of `nums` and M is the maximum value. The sieve takes O(M log log M). Calculating boundaries takes O(n^2). Sorting takes O(n log n). The final greedy selection takes O(n log k). The O(n^2) term dominates. · **Space:** O(M + n), where M is the maximum value in `nums` and n is the length of `nums`. This is for the sieve array (`O(M)`), and various arrays of size `n` (prime scores, counts, indices).
**Pros:** The logic is straightforward and easier to reason about compared to more optimized solutions.; It correctly breaks down the problem into contribution counting and greedy selection.
**Cons:** The O(n^2) complexity for finding boundaries is too slow for the given constraints (n <= 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The core of the algorithm is to first calculate the prime score for every number up to the maximum value in `nums`. This is done efficiently using a sieve. Then, for each element `nums[i]`, we determine its 'dominance range'. An element `nums[i]` is chosen from a subarray `[l, r]` if it has the highest prime score, with ties broken by the smallest index. This translates to finding the nearest element to its left with a greater or equal prime score (`L`) and the nearest element to its right with a strictly greater prime score (`R`).

In this naive approach, we find `L` and `R` for each `i` by iterating through the array, which takes O(n) time for each element, leading to an overall O(n^2) complexity for this step. The number of subarrays that will select `nums[i]` is then `(i - L) * (R - i)`.

After computing these counts for all elements, we have a collection of pairs `(nums[i], count[i])`. To maximize the final score, we greedily pick the largest numbers. We sort the elements `nums[i]` in descending order and, for each element, multiply it into our score `min(k, count[i])` times, using modular exponentiation for efficiency. We continue this process until we have performed `k` operations.

```java
class Solution {
    public int maximumScore(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] primeScores = new int[maxVal + 1];
        for (int i = 2; i <= maxVal; i++) {
            if (primeScores[i] == 0) { // i is prime
                for (long j = i; j <= maxVal; j += i) {
                    primeScores[(int)j]++;
                }
            }
        }

        int n = nums.length;
        int[] ps = new int[n];
        for (int i = 0; i < n; i++) {
            ps[i] = primeScores[nums[i]];
        }

        long[] counts = new long[n];
        for (int i = 0; i < n; i++) {
            int left = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (ps[j] >= ps[i]) {
                    left = j;
                    break;
                }
            }
            int right = n;
            for (int j = i + 1; j < n; j++) {
                if (ps[j] > ps[i]) {
                    right = j;
                    break;
                }
            }
            counts[i] = (long)(i - left) * (right - i);
        }

        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, (a, b) -> Integer.compare(nums[b], nums[a]));

        long score = 1;
        long MOD = 1_000_000_007;

        for (int i : indices) {
            if (k == 0) break;
            long num = nums[i];
            long count = counts[i];
            long timesToTake = Math.min(k, count);
            score = (score * power(num, timesToTake, MOD)) % MOD;
            k -= timesToTake;
        }

        return (int) score;
    }

    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1.  **Pre-compute Prime Scores:**
    *   Create an array `primeScores` of size `max_val + 1`, where `max_val` is the maximum possible value in `nums` (100001).
    *   Use a sieve method to populate this array. Iterate from `i = 2` to `max_val`. If `primeScores[i]` is 0, `i` is a prime. Then, for all multiples of `i` (i.e., `j = i, 2i, 3i, ...`), increment `primeScores[j]`.
2.  **Calculate Prime Scores for `nums`:**
    *   Create an array `ps` of size `n`, where `ps[i] = primeScores[nums[i]]`.
3.  **Calculate Contribution Counts (Naive):**
    *   For each index `i` from `0` to `n-1`:
        *   Find the left boundary `L`: Iterate `j` from `i-1` down to `0`. The first `j` where `ps[j] >= ps[i]` is `L`. If no such `j` exists, `L = -1`.
        *   Find the right boundary `R`: Iterate `j` from `i+1` up to `n-1`. The first `j` where `ps[j] > ps[i]` is `R`. If no such `j` exists, `R = n`.
        *   The number of times `nums[i]` can be chosen is `count[i] = (i - L) * (R - i)`.
4.  **Greedy Selection:**
    *   Create an array of indices `0, 1, ..., n-1`.
    *   Sort these indices in descending order based on the values in `nums`.
5.  **Calculate Final Score:**
    *   Initialize `score = 1`.
    *   Iterate through the sorted indices. For each index `i`:
        *   Determine how many times to take `nums[i]`: `times_to_take = min(k, count[i])`.
        *   Update the score: `score = (score * power(nums[i], times_to_take, MOD)) % MOD`, where `power` is a modular exponentiation function.
        *   Decrement `k` by `times_to_take`.
        *   If `k` becomes 0, break the loop.
    *   Return the final score.

## Optimized Contribution Count using Monotonic Stack
This approach follows the same high-level strategy as the brute-force method: calculate the contribution count for each element and then apply a greedy strategy. However, it significantly optimizes the most expensive step—the calculation of contribution counts. Instead of using O(n^2) nested loops to find the dominance boundaries for each element, this method employs a monotonic stack. This data structure allows us to find the 'previous greater or equal' and 'next greater' elements for all items in the array in a single pass, reducing the time complexity of this critical step from O(n^2) to O(n).
**Time:** O(n log n + M log log M + n log k). Sieve is O(M log log M). The monotonic stack part is O(n). Sorting is O(n log n). The final loop is O(n log k). This is dominated by O(n log n) or O(M log log M) depending on the inputs. · **Space:** O(M + n), where M is the maximum value in `nums` and n is the length of `nums`. Space is used for the sieve, prime score arrays, monotonic stack, and boundary arrays.
**Pros:** Highly efficient, with a time complexity that meets the problem constraints.; It's a classic and powerful application of the monotonic stack pattern for range-based problems.
**Cons:** The logic involving the monotonic stack can be less intuitive to come up with and implement correctly compared to the naive O(n^2) loops.
### Explanation
The overall structure of the solution remains the same: pre-compute prime scores, find contribution counts, and then greedily select the largest numbers. The key improvement lies in how we find the left and right boundaries (`L[i]` and `R[i]`) for each element `nums[i]`.

1.  **Finding Left Boundaries (`L`):** We iterate through the `ps` (prime scores) array from left to right. We use a stack that stores indices `j` such that `ps[j]` is in non-increasing order. For each `i`, we pop elements from the stack as long as their prime score is less than `ps[i]`. The element remaining at the top of the stack is the first one to the left of `i` with a prime score greater than or equal to `ps[i]`, which is our `L[i]`.

2.  **Finding Right Boundaries (`R`):** We do a similar pass from right to left. The stack will store indices `j` such that `ps[j]` is non-decreasing. For each `i`, we pop elements whose prime score is less than or equal to `ps[i]`. The top of the stack gives us the first element to the right of `i` with a strictly greater prime score, which is `R[i]`.

Each index is pushed and popped at most once in each pass, making this step `O(n)`. The rest of the algorithm, including sorting and the final product calculation, remains, but the overall complexity is now dominated by sorting, making it efficient enough for the given constraints.

```java
class Solution {
    public int maximumScore(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] primeScores = new int[maxVal + 1];
        for (int i = 2; i <= maxVal; i++) {
            if (primeScores[i] == 0) { // i is prime
                for (long j = i; j <= maxVal; j += i) {
                    primeScores[(int)j]++;
                }
            }
        }

        int n = nums.length;
        int[] ps = new int[n];
        for (int i = 0; i < n; i++) {
            ps[i] = primeScores[nums[i]];
        }

        // Calculate left boundaries (previous greater or equal)
        int[] left = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && ps[stack.peek()] < ps[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        // Calculate right boundaries (next greater)
        int[] right = new int[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && ps[stack.peek()] <= ps[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long[] counts = new long[n];
        for (int i = 0; i < n; i++) {
            counts[i] = (long)(i - left[i]) * (right[i] - i);
        }

        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, (a, b) -> Integer.compare(nums[b], nums[a]));

        long score = 1;
        long MOD = 1_000_000_007;

        for (int i : indices) {
            if (k == 0) break;
            long num = nums[i];
            long count = counts[i];
            long timesToTake = Math.min(k, count);
            score = (score * power(num, timesToTake, MOD)) % MOD;
            k -= timesToTake;
        }

        return (int) score;
    }

    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1.  **Pre-compute Prime Scores:** Same as the previous approach, using a sieve in `O(M log log M)` time.
2.  **Calculate Prime Scores for `nums`:** Create an array `ps` of size `n`, where `ps[i] = primeScores[nums[i]]`.
3.  **Optimized Boundary Calculation (Monotonic Stack):**
    *   To find the left boundaries `L[i]` (previous greater or equal element) for all `i`, iterate from left to right using a monotonic stack. This takes `O(n)`.
    *   To find the right boundaries `R[i]` (next greater element) for all `i`, iterate from right to left using a monotonic stack. This also takes `O(n)`.
4.  **Calculate Contribution Counts:** For each `i`, `count[i] = (long)(i - L[i]) * (R[i] - i)`. This takes `O(n)`.
5.  **Greedy Selection:** Same as the previous approach. Sort indices based on `nums` values.
6.  **Calculate Final Score:** Same as the previous approach. Iterate through sorted indices, apply modular exponentiation, and update `k`.

# Solutions
### Java

```java
class Solution {
private
  final int mod = (int)1 e9 + 7;
public
  int maximumScore(List<Integer> nums, int k) {
    int n = nums.size();
    int[][] arr = new int[n][0];
    for (int i = 0; i < n; ++i) {
      arr[i] = new int[]{i, primeFactors(nums.get(i)), nums.get(i)};
    }
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, -1);
    Arrays.fill(right, n);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int[] e : arr) {
      int i = e[0], f = e[1];
      while (!stk.isEmpty() && arr[stk.peek()][1] < f) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      int f = arr[i][1];
      while (!stk.isEmpty() && arr[stk.peek()][1] <= f) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        right[i] = stk.peek();
      }
      stk.push(i);
    }
    Arrays.sort(arr, (a, b)->b[2] - a[2]);
    long ans = 1;
    for (int[] e : arr) {
      int i = e[0], x = e[2];
      int l = left[i], r = right[i];
      long cnt = (long)(i - l) * (r - i);
      if (cnt <= k) {
        ans = ans * qpow(x, cnt) % mod;
        k -= cnt;
      } else {
        ans = ans * qpow(x, k) % mod;
        break;
      }
    }
    return (int)ans;
  }
private
  int primeFactors(int n) {
    int i = 2;
    Set<Integer> ans = new HashSet<>();
    while (i <= n / i) {
      while (n % i == 0) {
        ans.add(i);
        n /= i;
      }
      ++i;
    }
    if (n > 1) {
      ans.add(n);
    }
    return ans.size();
  }
private
  int qpow(long a, long n) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumScore(vector<int> &nums, int k) {
    const int mod = 1e9 + 7;
    int n = nums.size();
    vector<tuple<int, int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = {i, primeFactors(nums[i]), nums[i]};
    }
    vector<int> left(n, -1);
    vector<int> right(n, n);
    stack<int> stk;
    for (auto [i, f, _] : arr) {
      while (!stk.empty() && get<1>(arr[stk.top()]) < f) {
        stk.pop();
      }
      if (!stk.empty()) {
        left[i] = stk.top();
      }
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      int f = get<1>(arr[i]);
      while (!stk.empty() && get<1>(arr[stk.top()]) <= f) {
        stk.pop();
      }
      if (!stk.empty()) {
        right[i] = stk.top();
      }
      stk.push(i);
    }
    sort(arr.begin(), arr.end(), [](const auto &lhs, const auto &rhs) {
      return get<2>(rhs) < get<2>(lhs);
    });
    long long ans = 1;
    auto qpow = [&](long long a, int n) {
      long long ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return ans;
    };
    for (auto [i, _, x] : arr) {
      int l = left[i], r = right[i];
      long long cnt = 1LL * (i - l) * (r - i);
      if (cnt <= k) {
        ans = ans * qpow(x, cnt) % mod;
        k -= cnt;
      } else {
        ans = ans * qpow(x, k) % mod;
        break;
      }
    }
    return ans;
  }
  int primeFactors(int n) {
    int i = 2;
    unordered_set<int> ans;
    while (i <= n / i) {
      while (n % i == 0) {
        ans.insert(i);
        n /= i;
      }
      ++i;
    }
    if (n > 1) {
      ans.insert(n);
    }
    return ans.size();
  }
};

```

### Python

```python
def primeFactors ( n ): i = 2 ans = set () while i * i <= n : while n % i == 0 : ans . add ( i ) n //= i i += 1 if n > 1 : ans . add ( n ) return len ( ans ) class Solution : def maximumScore ( self , nums : List [ int ], k : int ) -> int : mod = 10 ** 9 + 7 arr = [( i , primeFactors ( x ), x ) for i , x in enumerate ( nums )] n = len ( nums ) left = [ - 1 ] * n right = [ n ] * n stk = [] for i , f , x in arr : while stk and stk [ - 1 ][ 0 ] < f : stk . pop () if stk : left [ i ] = stk [ - 1 ][ 1 ] stk . append (( f , i )) stk = [] for i , f , x in arr [:: - 1 ]: while stk and stk [ - 1 ][ 0 ] <= f : stk . pop () if stk : right [ i ] = stk [ - 1 ][ 1 ] stk . append (( f , i )) arr . sort ( key = lambda x : - x [ 2 ]) ans = 1 for i , f , x in arr : l , r = left [ i ], right [ i ] cnt = ( i - l ) * ( r - i ) if cnt <= k : ans = ans * pow ( x , cnt , mod ) % mod k -= cnt else : ans = ans * pow ( x , k , mod ) % mod break return ans
```