Maximum Score from Performing Multiplication Operations

Hard
1482.

Maximum Score from Performing Multiplication Operations

Maximum Score from Performing Multiplication Operations is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

You are given nums of length n and multipliers of length m, with m <= n. Starting from a score of 0, perform exactly m operations; in the i-th operation (0-indexed):

  • remove one element x from either end of nums (the first or the last remaining element), and
  • add multipliers[i] * x to the score.

Return the maximum score reachable after all m operations.

Example 1

Input
nums = [1,2,3], multipliers = [3,2,1]
Output
14
Explanation
Take 3, 2, 1 from the right: 9 + 4 + 1.

Example 2

Input
nums = [4,-2,5], multipliers = [2,-1]
Output
12
Explanation
Take 5 (+10), then -2 from the right (+2).

Example 3

Input
nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output
102

Constraints

  • n == nums.length
  • m == multipliers.length
  • 1 <= m <= 300
  • m <= n <= 10^5
  • -1000 <= nums[i], multipliers[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} multipliers
 * @return {number}
 */
var maximumScore = function(nums, multipliers) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Score from Performing Multiplication Operations Solution

Maximum Score from Performing Multiplication Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Score from Performing Multiplication Operations is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given nums of length n and multipliers of length m, with m <= n. Starting from a score of 0, perform exactly m operations; in the i-th operation (0-indexed):

  • remove one element x from either end of nums (the first or the last remaining element), and
  • add multipliers[i] * x to the score.

Return the maximum score reachable after all m operations.

Example 1

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: Take 3, 2, 1 from the right: 9 + 4 + 1.

Example 2

Input: nums = [4,-2,5], multipliers = [2,-1]
Output: 12
Explanation: Take 5 (+10), then -2 from the right (+2).

Example 3

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102

Constraints

  • n == nums.length
  • m == multipliers.length
  • 1 <= m <= 300
  • m <= n <= 10^5
  • -1000 <= nums[i], multipliers[i] <= 1000

Hints for Maximum Score from Performing Multiplication Operations

  1. Hint 1

    Greedy choices fail — a big product now can leave terrible elements for later.

  2. Hint 2

    After i operations, if left of them took from the front, the remaining array is fixed: it starts at left and ends at n - 1 - (i - left).

  3. Hint 3

    So the state is (i, left) — only O(m²) states, even though n is large. Take the better of front and back at each state.

How to solve Maximum Score from Performing Multiplication Operations

The removed elements always form a prefix and a suffix of nums. After i operations with left taken from the front, the right pointer is n - 1 - (i - left), so (i, left) describes the state completely and there are only about m²/2 of them.

Approach

  1. Let dp[i][left] be the best score obtainable from operations i..m-1 when left elements have been taken from the front.
  2. dp[m][*] = 0.
  3. For i from m-1 down to 0 and left from 0 to i: with right = n - 1 - (i - left), dp[i][left] = max(multipliers[i]·nums[left] + dp[i+1][left+1], multipliers[i]·nums[right] + dp[i+1][left]).
  4. Return dp[0][0]; a single row of size m + 1 suffices if left is processed in increasing order.

Why it works

Every play sequence is a sequence of front/back choices, and its future depends only on how many of each were made — exactly (i, left). The recurrence tries both choices and adds the optimal continuation, so it equals the best total over all sequences.

Complexity

  • Time — O(m²)
  • Space — O(m)

Pitfalls

  • Indexing the DP by both ends (O(n²)) is too slow and too large when n = 10^5; index by operations and front-count instead.
  • Values are negative too, so initialise maxima carefully (no 0 floor).
  • The answer is at most 300 · 10^6, which fits in 32 bits.

Reference solution

Python

from typing import List

def maximumScore(nums: List[int], multipliers: List[int]) -> int:
    n, m = len(nums), len(multipliers)
    dp = [0] * (m + 1)
    for i in range(m - 1, -1, -1):
        mu = multipliers[i]
        for left in range(i + 1):
            right = n - 1 - (i - left)
            a = mu * nums[left] + dp[left + 1]
            b = mu * nums[right] + dp[left]
            dp[left] = a if a > b else b
    return dp[0]

Java

public static int maximumScore(int[] nums, int[] multipliers) {
    int n = nums.length, m = multipliers.length;
    int[] dp = new int[m + 1];
    for (int i = m - 1; i >= 0; i--) {
        int mu = multipliers[i];
        for (int left = 0; left <= i; left++) {
            int right = n - 1 - (i - left);
            int a = mu * nums[left] + dp[left + 1];
            int b = mu * nums[right] + dp[left];
            dp[left] = Math.max(a, b);
        }
    }
    return dp[0];
}

C++

int maximumScore(vector<int>& nums, vector<int>& multipliers) {
    int n = nums.size(), m = multipliers.size();
    vector<int> dp(m + 1, 0);
    for (int i = m - 1; i >= 0; i--) {
        int mu = multipliers[i];
        for (int left = 0; left <= i; left++) {
            int right = n - 1 - (i - left);
            int a = mu * nums[left] + dp[left + 1];
            int b = mu * nums[right] + dp[left];
            dp[left] = max(a, b);
        }
    }
    return dp[0];
}

JavaScript

var maximumScore = function(nums, multipliers) {
    var n = nums.length, m = multipliers.length;
    var dp = new Array(m + 1).fill(0);
    for (var i = m - 1; i >= 0; i--) {
        var mu = multipliers[i];
        for (var left = 0; left <= i; left++) {
            var right = n - 1 - (i - left);
            var a = mu * nums[left] + dp[left + 1];
            var b = mu * nums[right] + dp[left];
            dp[left] = a > b ? a : b;
        }
    }
    return dp[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming