Maximum Score from Performing Multiplication Operations: DP on Two Ends

You are given an integer array nums of size n and an integer array multipliers of size m. You perform m operations. In the ith operation, you choose an element from either the left end or the right end of nums, multiply it by multipliers[i], and add the result to your total score. The chosen element is then removed from nums. Return the maximum score you can achieve after all m operations.

This is LeetCode 1770: Maximum Score from Performing Multiplication Operations, and it is one of the best problems for learning how to define DP states on endpoints of an array. The technique it teaches applies to any problem where you make sequential choices from the two ends of a sequence.

Why this problem matters

At first glance, this looks like a greedy problem: just pick whichever end gives the bigger product. But greedy fails here. Picking a smaller value now might leave a larger value available for a bigger multiplier later. The decisions are entangled across operations, which is exactly the situation where dynamic programming shines.

This problem teaches a clean DP pattern that you will see again in problems involving interval choices, two-pointer DP, and sequential decisions on array endpoints. Once you internalize the state definition, the same idea transfers directly to problems like "Stone Game" (LeetCode 877) and its many variants.

The key insight

You do not need to track the entire remaining subarray. Since elements are only removed from the left or right end, the remaining elements always form a contiguous subarray of the original nums. If you know how many elements you have taken from the left, and which operation you are on, you can figure out how many you took from the right.

Define dp[i][left] as the maximum score achievable from operation i onward, given that you have already taken left elements from the left side. The number of elements taken from the right is i - left, so the current left end is nums[left] and the current right end is nums[n - 1 - (i - left)].

The recurrence:

1. Pick from the left: multipliers[i] * nums[left] + dp[i + 1][left + 1]
2. Pick from the right: multipliers[i] * nums[n - 1 - (i - left)] + dp[i + 1][left]
3. Take the max of both choices.

Base case: when i == m, all operations are done, so dp[m][left] = 0 for all valid left.

The solution

def maximum_score(nums: list[int], multipliers: list[int]) -> int:
    n = len(nums)
    m = len(multipliers)
    dp = [[0] * (m + 1) for _ in range(m + 1)]

    for i in range(m - 1, -1, -1):
        for left in range(i, -1, -1):
            right = n - 1 - (i - left)
            pick_left = multipliers[i] * nums[left] + dp[i + 1][left + 1]
            pick_right = multipliers[i] * nums[right] + dp[i + 1][left]
            dp[i][left] = max(pick_left, pick_right)

    return dp[0][0]

Let's walk through what each piece does.

The table dp has dimensions (m + 1) x (m + 1). The extra row at i = m serves as the base case where all operations are complete and the score contribution is 0.

The outer loop iterates operations in reverse, from m - 1 down to 0. This is bottom-up DP: we compute later operations first so their results are ready when we need them for earlier operations.

The inner loop iterates over all valid values of left for a given operation i. At operation i, you can have taken at most i elements from the left (and the rest from the right), so left ranges from 0 to i.

For each state, we compute the index of the right end as n - 1 - (i - left). The term i - left is how many elements have been taken from the right, so n - 1 - (i - left) gives the current rightmost available element.

We evaluate both choices (pick left or pick right), take the maximum, and store it. The final answer is dp[0][0], which is the maximum score starting from operation 0 with 0 elements taken from the left.

Visual walkthrough

Notice how the DP evaluates both choices at each step. Taking 6 from the right first (12 points) is better than taking 1 from the left (2 points), even though the greedy comparison at each step is not always correct in isolation. The DP considers the downstream consequences: saving the 5 for the last multiplier of 1, and spending the cheap 1 on the multiplier of 3, gives the globally optimal score of 20.

Complexity analysis

Time is O(m^2) where m is the length of the multipliers array. The outer loop runs m iterations. The inner loop runs at most i + 1 iterations for operation i, summing to 1 + 2 + ... + m = m(m+1)/2, which is O(m^2). Each state does O(1) work.

Space is O(m^2) for the DP table. You can optimize this to O(m) by observing that row i only depends on row i + 1, so you can use two 1D arrays and alternate between them. But the O(m^2) version is clean and passes comfortably.

The building blocks

1. Deriving the right pointer from the left pointer

right = n - 1 - (i - left)

This is the core trick of the problem. When you have made i total picks and left of them came from the left side, then i - left came from the right side. The rightmost available element is at index n - 1 - (i - left). This eliminates the need for a separate right dimension in the DP, cutting the state space dramatically. You will see this same "derive one variable from the others" pattern in any DP where the state variables are not all independent.

2. Bottom-up DP on operations

for i in range(m - 1, -1, -1):
    for left in range(i, -1, -1):
        pick_left = multipliers[i] * nums[left] + dp[i + 1][left + 1]
        pick_right = multipliers[i] * nums[right] + dp[i + 1][left]
        dp[i][left] = max(pick_left, pick_right)

The reverse iteration is standard for bottom-up DP. By filling in later operations first, every lookup into dp[i + 1][...] references a value that is already computed. The max of the two branches captures the optimal choice at each state. This "fill backward, look forward" pattern appears in virtually every sequence DP problem, from coin change to edit distance to longest increasing subsequence.

Edge cases

• m equals 1: only one operation. Pick the max of nums[0] and nums[n-1], multiply by multipliers[0].
• m equals n: you must pick every element. The DP still applies, you just have more operations to fill.
• Negative numbers in nums or multipliers: the DP handles this naturally. Picking a negative number with a negative multiplier produces a positive score, so the max/min reasoning still works through the recurrence.
• All multipliers are the same: the order of picking does not matter for the multiplier, but it still matters which elements you pick. The DP degenerates to choosing the m elements with the largest absolute values from the ends.
• n is very large, m is small: this is exactly why the O(m^2) solution works. Even if n is 100,000, if m is only 1,000, the DP table is just 1,000 x 1,000.

From understanding to recall

You now understand why the DP state is (operation, left_count) and how the right pointer is derived. The recurrence is short, the base case is trivial, and the implementation is under 15 lines. But reproducing this under time pressure is a different skill.

The details that trip people up: which direction do you iterate? What is the exact formula for the right index? Is it n - 1 - (i - left) or n - (i - left)? Does left range from 0 to i or 0 to i - 1? These are not conceptual misunderstandings. They are recall gaps, and they cost time in interviews.

Spaced repetition closes them. You practice writing the state definition, the right-pointer derivation, and the bottom-up loop from memory. After a few rounds, the formula n - 1 - (i - left) is automatic. You see "pick from two ends" in a problem statement, and the DP template flows out without hesitation.

Related posts

• Coin Change - The classic bottom-up DP problem that teaches table-filling and optimal substructure
• Edit Distance - Two-dimensional DP where each cell depends on neighboring cells, the same fill pattern used here
• Burst Balloons - Another hard DP problem where the key insight is reframing which choice to reason about (last burst vs. first pick)

CodeBricks breaks Maximum Score from Performing Multiplication Operations into its endpoint-derivation and bottom-up DP building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an endpoint DP problem shows up in your interview, you do not think about it. You just write it.