Maximum score from performing multiplication operations

Array Dynamic Programming

43.2% acceptance

Feb 25, 2026

2592

514

You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m. You begin with a score of 0. You want to perform exactly m operations. On the ith operation you will: Choose one integer x from either the start or the end of the array nums. Add multipliers[i] * x to your score. Remove x from nums. Return the maximum score after performing m operations.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score(nums: Vec<i32>, multipliers: Vec<i32>) -> i32 {
    let n = nums.len();
    let m = multipliers.len();
    // dp[i][j] = max score after i ops, took j from left, i-j from right
    let mut dp = vec![vec![i32::MIN; m + 1]; m + 1];
    dp[0][0] = 0;
    let mut ans = i32::MIN;
    for i in 1..=m {
      let mult = multipliers[i - 1];
      for j in 0..=i {
        let r = i - j; // from right
        dp[i][j] = i32::MIN;
        // Took from left (j > 0): dp[i-1][j-1] + nums[j-1]*mult
        if j > 0 && dp[i-1][j-1] != i32::MIN {
          dp[i][j] = dp[i][j].max(dp[i-1][j-1] + nums[j-1] * mult);
        }
        // Took from right (r > 0): dp[i-1][j] + nums[n-r]*mult
        if r > 0 && dp[i-1][j] != i32::MIN {
          dp[i][j] = dp[i][j].max(dp[i-1][j] + nums[n - r] * mult);
        }
        if i == m {
          ans = ans.max(dp[i][j]);
        }
      }
    }
    ans
  }
}