We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Score from Performing Multiplication Operations

Number: 1896

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

You are given two integer arrays, nums and multipliers. You must perform exactly m operations. In each operation, choose a number from either the start or the end of nums, multiply it by the current multiplier, add it to your score, and remove that number. The goal is to maximize the score after m operations.

Key Insights

  • The number of operations (m) is much smaller than the size of nums.
  • Only the first m operations matter, so we can focus our DP state on the number of operations performed.
  • Define a state with two variables: the current operation index (i) and the count of elements picked from the start.
  • The index picked from the end can be deduced since the total picks so far minus the left picks gives the number of elements taken from the end.
  • Recurrence: At each step, decide between taking from the left or taking from the right and add the corresponding score.
  • Use memoization (or bottom-up DP) to avoid redundant computations.

Space and Time Complexity

Time Complexity: O(m^2) – We have m*(m+1)/2 states and each state is computed in constant time. Space Complexity: O(m^2) – For the memoization/dynamic programming table storing results for each state.

Solution

We use dynamic programming with memoization. Define a function dp(operation, left) that returns the maximum score achievable from the current state, where operation is the current step (0-indexed) and left is the number of elements taken from the start. The number of elements taken from the end is operation - left. At each state, calculate the index to pick from the right as (n - 1 - (operation - left)). The recurrence relation is:
dp(operation, left) = max( multipliers[operation] * nums[left] + dp(operation + 1, left + 1), multipliers[operation] * nums[right] + dp(operation + 1, left) )
where right = n - 1 - (operation - left).
The answer is dp(0, 0).

Code Solutions

# Python solution with line-by-line comments

def maximumScore(nums, multipliers):
    # Total number of operations
    m = len(multipliers)
    n = len(nums)
    
    # Use memoization cache to store computed states
    memo = {}
    
    # Define the DP function with current operation and left count
    def dp(operation, left):
        # Base case: if all operations are done, return 0
        if operation == m:
            return 0
        # Check if result is already computed
        if (operation, left) in memo:
            return memo[(operation, left)]
        
        # Calculate index from the right based on current state
        right_index = n - 1 - (operation - left)
        
        # Option1: Pick from the left
        left_pick = multipliers[operation] * nums[left] + dp(operation + 1, left + 1)
        # Option2: Pick from the right
        right_pick = multipliers[operation] * nums[right_index] + dp(operation + 1, left)
        
        # Get maximum result from both choices and store in memo
        memo[(operation, left)] = max(left_pick, right_pick)
        return memo[(operation, left)]
    
    # Start the recursion from operation 0 with 0 left picks
    return dp(0, 0)

# Example usage:
# print(maximumScore([1,2,3], [3,2,1]))  # Output: 14
← Back to All Questions