Maximum Score from Performing Multiplication Operations

Published: Sep 16, 2022

Medium Dynamic Programming

Introduction

At a glance, it looks a greedy problem. However, if we look at the examples, we learn the greedy approach doesn’t work. So, this is a dynamic programming problem.

Problem Description

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), you will:

  • Choose one integer x from either the start or the end of the array nums.
  • Add multipliers[i] * x to your score.
  • Remove x from the array nums.

Return the maximum score after performing m operations.

Constraints:

  • n == nums.length
  • m == multipliers.length
  • 1 <= m <= 10**3
  • m <= n <= 10**5
  • -1000 <= nums[i], multipliers[i] <= 1000

https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/

Examples

Example 1:
Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
3 * 3 + 2 * 2 + 1 * 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:
-5 * -10 + -3 * -5 + -3 * 3 + 1 * 4 + 7 * 6 = 102
Notice, the third multiplication is -3 * 3 not 1 * 3.

Analysis

Among a couple dynamic programming approaches, the solution here uses bottom-up tabular approach. The 2D array saves a maximum score so far. Starting from multiplier operation from right to left, compare the calculation with nums from left and right. The calculation with nums from left, it sees previous row’s right column as a previous score. While the calculation with num from right, it sees previous row’s same column as a previous score. When the calculation ends, the answer is on the cell (0, 0).

Solution

class MaximumScoreFromPerformingMultiplicationOperations:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        m, n = len(multipliers), len(nums)
        memo = [[0 for _ in range(m + 1)] for _ in range(m + 1)]
        for i in range(m - 1, -1 ,-1):
            for j in range(i, -1, -1):
                memo[i][j] = max(nums[j] * multipliers[i] + memo[i + 1][j + 1],
                                nums[n - 1 - (i - j)] * multipliers[i] + memo[i + 1][j])
        return memo[0][0]

Complexities

  • Time: O(m^2)
  • Space: O(m^2)