Skip to main content
Talentd

Maximum Score from Performing Multiplication Operations - Solution & Explanation

HardArrayDynamic Programming17 min readAsked at: Google
Practice this problem

Problem Statement

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 (0-indexed) you will:

  • Choose one integer x from either the start or the end of the array nums.
  • Add multipliers[i] * x to your score.
    • Note that multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.
  • Remove x from nums.

Return the maximum score after performing m operations.

 

Example 1:

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2:

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

 

Constraints:

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

Approach Overview

Problem Overview: You have an array nums and another array multipliers. For each multiplier, you choose either the leftmost or rightmost value from nums, multiply it with the current multiplier, and add it to the score. The goal is to maximize the final score after performing exactly m operations.

Approach 1: Greedy Choice from Ends (O(m) time, O(1) space)

A straightforward idea is to always pick the larger product between nums[left] * multipliers[i] and nums[right] * multipliers[i]. You maintain two pointers at the start and end of the array and move the pointer corresponding to the chosen value. This runs in O(m) time since each operation makes one decision. The limitation: local decisions do not guarantee a global optimum. A smaller product early might enable a larger combination later, so this approach fails on many cases but helps build intuition for the problem structure.

Approach 2: Dynamic Programming on Picks (O(m²) time, O(m²) space)

The optimal solution uses dynamic programming. At operation i, you have taken some numbers from the left and some from the right. If l numbers were taken from the left, then i - l were taken from the right. This state uniquely determines the remaining subarray. Define dp[i][l] as the maximum score after i operations with l picks from the left.

From this state, you have two choices: take the next number from the left or from the right. The right index can be derived as n - 1 - (i - l). Transition by computing both options and taking the maximum. Because i ranges up to m and l ranges up to m, the total states are O(m²). Each state does constant work, giving O(m²) time complexity. This technique is a classic interval-style DP frequently seen in array and decision problems.

The DP can be implemented with top-down memoization or bottom-up tabulation. Many implementations compress space to O(m) because each step only depends on the next layer.

Recommended for interviews: The dynamic programming approach is what interviewers expect. The greedy strategy shows you recognize the two-end choice pattern, but the DP solution demonstrates that you can model state transitions and optimize overlapping subproblems. Problems combining dynamic programming with array decisions appear frequently in Google, Amazon, and Meta interviews.

Approach 1: Dynamic Programming Approach

This approach involves using dynamic programming to keep track of the maximum scores obtainable by choosing elements from either the start or the end of the nums array during each step of the operations defined by the multipliers array. We maintain a 2D DP table where dp[i][j] represents the maximum score obtained by using the first (i + j) elements from nums, where i elements have been chosen from the start, and j elements have been chosen from the end.

The function maximum_score initializes a 2D array dp with dimensions (m+1) x (m+1). We iterate through the operations and the elements chosen from the start. For each combination of choices, we compute the score achievable by either picking from the start or end. We fill up the DP table backwards, taking the maximum of both potential choices.

Code

PythonC++JavaCJavaScriptC#

Python

C++

Java

C

JavaScript

C#

Complexity

Time Complexity: O(m^2), where m is the length of the multipliers array, because we're filling an m x m DP table.
Space Complexity: O(m^2) due to the storage requirements of the m x m DP table.

Try this approach in the editor →

Approach 2: Greedy Approach

This approach uses a simpler greedy strategy to try and choose the best possible option at each step, based on examining both the start and end of the nums array for potential scores. It evaluates which element, when multiplied with the current multiplier, gives the maximum increase in the score and selects that iteratively through all operations.

The function computes the maximum playable score using a greedy method that goes through each multiplier in the multipliers array. At each step, it determines whether picking the starting element or the ending element in the nums array yields a better score and then opts for that choice until all operations are exhausted.

Code

PythonC++JavaCJavaScriptC#

Python

C++

Java

C

JavaScript

C#

Complexity

Time Complexity: O(m), where m is the number of operations.
Space Complexity: O(1), utilizing constant space regardless of input size.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(m^2), where m is the length of the multipliers array, because we're filling an m x m DP table.
Space Complexity: O(m^2) due to the storage requirements of the m x m DP table.

Greedy Approach

Time Complexity: O(m), where m is the number of operations.
Space Complexity: O(1), utilizing constant space regardless of input size.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Pick from EndsO(m)O(1)Quick heuristic or intuition building, but not guaranteed optimal
Dynamic Programming (State: operations, left picks)O(m²)O(m²) or O(m) optimizedGeneral optimal solution for all inputs; standard interview approach

Video Solution

Leetcode 1770. Maximum Score from Performing Multiplication Operations • Fraz • 11,418 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Score from Performing Multiplication Operations easy or hard?
The problem is rated Hard because greedy intuition alone fails and the correct solution requires defining a non‑obvious DP state. Candidates must reason about how left and right picks affect the remaining array and design an O(m^2) dynamic programming solution.
How to solve Maximum Score from Performing Multiplication Operations in O(m^2)?
Define dp[i][l] as the maximum score after performing i operations and taking l numbers from the left. The right index becomes n - 1 - (i - l). For each state, compute the maximum between picking from the left or the right using the current multiplier. Filling all states results in an O(m^2) dynamic programming solution.
Maximum Score from Performing Multiplication Operations Python or Java solution?
The solution is typically implemented using dynamic programming with memoization or bottom-up tabulation. Python often uses recursion with functools.lru_cache, while Java implementations commonly use a 2D DP array or optimized 1D rolling array.
What is the best approach for Maximum Score from Performing Multiplication Operations?
Dynamic Programming is the optimal approach. Track the number of operations performed and how many elements were taken from the left side of the array. This state determines the remaining right index and allows computing the maximum score through two choices. The overall complexity is O(m^2) time where m is the number of multipliers.
Is Maximum Score from Performing Multiplication Operations asked at Google/Amazon/Meta?
This problem follows a classic dynamic programming pattern involving decisions from both ends of an array. Variations of this pattern appear in interviews at companies such as Google, Amazon, and Meta because they test state modeling, DP transitions, and optimization of overlapping subproblems.
What data structure is used in Maximum Score from Performing Multiplication Operations?
The core structure is a dynamic programming table or memoization cache. It stores intermediate results for states defined by the number of operations performed and the number of elements taken from the left side of the array.
What is the time complexity of Maximum Score from Performing Multiplication Operations?
The optimal dynamic programming solution runs in O(m^2) time and O(m^2) space, where m is the number of multipliers. Each DP state represents a pair (operations performed, elements taken from the left). Since there are roughly m * m states and each transition takes constant time, the total complexity becomes quadratic in m.

Ready to solve this problem?

Practice Maximum Score from Performing Multiplication Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Points You Can Obtain from Cards

Next

Maximum Spending After Buying Items