How to solve the Maximum Score from Performing Multiplication Operations Problem

5 min readMay 7, 2022

This is a explanation of this LeetCode Problem. Please visit the link to read the question.

How to approach this problem

If a problem that asks to find a maximum, minimum or number of ways to do a certain task you might want to consider dynamic programming or a greedy algorithm. So try to find subproblems. If the future decisions depend on previous decisions then you should think of dynamic programming, if not, then it’s ok to use greedy algorithms.

For this problem, we will have to use dynamic programming because we can’t just pick the number that give a higher score at each round, we need to be more strategic and consider what options there would be in the future.

We will follow a dynamic programming framework that I like to use:

Define a function or data structure that gives an answer for a certain state
Find the recurrence relation to connect the states
Find the base cases

It would be easy to think about a decision tree first. We have 2 options for each round: pick left or pick right. So our decision tree will have two branches for each node, and give us m² cases where m is the length of the multiplier array.

In the simple example above, the green numbers represent the scores that can be gained if you pick the pink numbers. The answer would be 18 because picking right for round 1 gives 12 points, and picking right again for round 2 will give us 6 points, which gives us the highest score of all cases.

Now let’s follow the dynamic programming framework to solve this problem.

STEP 1. Define a function or data structure

First, we need to see what the state variables is, because that’s going to be the input for the function. Each state, we will have a different “middle part” of the numsarray to process on. That subarray can be defined as how many operations we’ve done so far, and how many of the left or right we’ve deleted. We will only choose i and left where i is the number of operations we’ve done so far, and left as how many did we pick from the left. We also need to know how many we picked from the right (end of the array) but we can calculate this with i and left.

The output of our function will be the maximum score for that given state. For example, after we conducted 3 operations, where we picked 2 from the left and 1 from the right, the maximum score will be dp(3,2) .

If you wish to do a Top-down approach using recursion and memoization, you would put i and left as the input for the recursive function. If you wish to do a Bottom-up iteration you would use a 2D array and store the output atdp[i, left]. This article will first use the top-down approach, then change the code to the bottom-up approach, because iteration is generally considered to be more efficient than using recursion.

STEP 2. Find the recurrence relation between each state

Think about what decisions needs to be made to get from a state to the next. At each stage we have two choices: pick the left element of nums or to pick the right. We just need to pick the one that contributes more than the other.

Choosing the left:
Current maximum score dp(i,left)
Next maximum score dp(i+1,left+1)

Choosing the right:
Current maximum score dp(i,left)
Next maximum score dp(i+1,left)

When we are deciding what to pick at round 0, we should be picking 4 not because 12 points is higher than 3 points, but because 6+12 points is higher than 8 + 3 points. We can get the maximum score of 18 by comparing the total score that each sibling gathered so far, from the bottom of the tree to the top.

The score up until the current round can be represented as:

int maxScore = Math.max(
    multiplier[i] * nums[left]  + dp(i+1,left+1),
    multiplier[i] * nums[right] + dp(i+1,left)));

where right = nums.length - 1 - (i-left)

STEP 2. Base Cases

For the base cases we need to think about what happens at the bottom of the tree. When i becomes the length of multiplier we stop the recursive calls and return 0 so that the maximum score of the last round can become the larger of multiplier[i] * nums[left] and multiplier[i] * nums[right] . For example, dp(0,1) = Math.max(2 * 1 + dp(0,2) 2 * 3 + dp(0,1)) which is 6 if dp(0,2) and dp(0,1) are 0. That’s why we need to return 0 when i becomes the length of multiplier .

Solution for top-down recursion with memoization

Solution for bottom-up iteration

This solution is taking the top-down recursion and changing it to a bottom-up iteration. We keep the original recurrence relation, but we need to be careful about what order the iteration will take place. We need to iterate from the last round to the 0th round and return memo[0][0] at the end. In addition, to prevent going out of bounds, the memo array will have an additional row and column which will be initially filled with 0s.

Time and Space Complexity

Generally, in dynamic programming the time complexity would follow the number of possible states (if there is some kind of memoization or tabulation to avoid repeated computations)

The time and space complexity for this problem is O(n²) where n is the length of the multipliers array. This goes for both approaches, top-down and bottom-up.