Skip to main content

1770 - Maximum Score from Performing Multiplication Operations

Difficulty: Hard | Pattern: Dynamic Programming (2D) | Company tags: Amazon, Google

Problem Statement​

You are given two integer arrays nums and multipliers of size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the i-th operation (1-indexed):

  • Choose one integer x from either the start or the end of nums.
  • Add multipliers[i] * x to your score.
  • 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: [3×3, 2×2, 1×1] = 9+4+1=14 (take from end each time)

Example 2:

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

Approach: Top-Down DP (Memoization) — O(m²)​

Key insight: After i operations where l were taken from the left, then i - l were taken from the right. State = (i, l) uniquely defines the remaining array's pointers.

dp(i, l) = max score from operation i onward, given l elements taken from left so far.

from functools import lru_cache

def maximumScore(nums: list[int], multipliers: list[int]) -> int:
    n, m = len(nums), len(multipliers)
    
    @lru_cache(maxsize=None)
    def dp(i, l):
        if i == m:
            return 0
        r = i - l  # elements taken from right so far
        mult = multipliers[i]
        
        # Option 1: take from left
        take_left = mult * nums[l] + dp(i + 1, l + 1)
        # Option 2: take from right
        take_right = mult * nums[n - 1 - r] + dp(i + 1, l)
        
        return max(take_left, take_right)
    
    return dp(0, 0)

Bottom-Up DP​

def maximumScore(nums: list[int], multipliers: list[int]) -> int:
    n, m = len(nums), len(multipliers)
    dp = [[0] * (m + 1) for _ in range(m + 1)]
    
    for i in range(m - 1, -1, -1):
        for l in range(i, -1, -1):
            r = i - l
            mult = multipliers[i]
            dp[i][l] = max(
                mult * nums[l] + dp[i+1][l+1],       # take left
                mult * nums[n-1-r] + dp[i+1][l]      # take right
            )
    
    return dp[0][0]

State Derivation​

After i total operations:

  • l taken from left → the leftmost available is nums[l]
  • i - l taken from right → the rightmost available is nums[n - 1 - (i-l)]

So (i, l) fully describes the state with only O(m²) distinct states.

Algorithm Flow​

Complexity​

  • Time: O(m²) — m² states, O(1) per state
  • Space: O(m²) for memoization table