Apply operations to maximize score

Array Math Stack Greedy Sorting Monotonic Stack Number Theory

53.7% acceptance

Feb 25, 2026

772

127

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score(nums: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();

    fn prime_score(mut x: i32) -> i32 {
      let mut cnt = 0;
      let mut d = 2;
      while d * d <= x { if x % d == 0 { cnt += 1; while x % d == 0 { x /= d; } } d += 1; }
      if x > 1 { cnt += 1; }
      cnt
    }

    fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 { if exp % 2 == 1 { result = result * base % modulus; } exp /= 2; base = base * base % modulus; }
      result
    }

    let scores: Vec<i32> = nums.iter().map(|&v| prime_score(v)).collect();

    // L[i] = i - left[i], left[i] = last j < i with scores[j] >= scores[i] (-1 if none)
    let mut left = vec![-1i64; n];
    let mut stack: Vec<usize> = vec![];
    for i in 0..n {
      while let Some(&top) = stack.last() {
        if scores[top] < scores[i] { stack.pop(); } else { left[i] = top as i64; break; }
      }
      stack.push(i);
    }

    // R[i] = right[i] - i, right[i] = first j > i with scores[j] > scores[i] (n if none)
    let mut right = vec![n as i64; n];
    let mut stack: Vec<usize> = vec![];
    for i in (0..n).rev() {
      while let Some(&top) = stack.last() {
        if scores[top] <= scores[i] { stack.pop(); } else { right[i] = top as i64; break; }
      }
      stack.push(i);
    }

    let mut items: Vec<(i32, i64)> = (0..n)
      .map(|i| (nums[i], (i as i64 - left[i]) * (right[i] - i as i64)))
      .collect();
    items.sort_by(|a, b| b.0.cmp(&a.0));

    let mut score = 1i64;
    let mut remaining = k as i64;
    for (val, count) in items {
      if remaining <= 0 { break; }
      let take = remaining.min(count);
      score = score * pow_mod(val as i64, take, MOD) % MOD;
      remaining -= take;
    }
    score as i32
  }
}