LeetCode 1770 - Maximum Score from Performing Multiplication Operations

This problem asks us to maximize a score obtained by performing a sequence of exactly m operations on an array nums of length n using multipliers from another array multipliers of length m.

leetcodehardarraydynamic-programming

LeetCode Problem 1770

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to maximize a score obtained by performing a sequence of exactly m operations on an array nums of length n using multipliers from another array multipliers of length m. In each operation, we can pick an element either from the start or end of nums, multiply it by the current multiplier, add the result to the running score, and remove the element from nums. The objective is to maximize the total score after m operations.

The inputs are two arrays: nums represents the pool of numbers we can pick from, and multipliers represents the sequence of factors applied at each operation. The output is a single integer, the maximum achievable score. The constraints 1 <= m <= 300 and m <= n <= 10^5 indicate that while the nums array can be large, the number of operations is small. This suggests that an efficient algorithm should focus on the m operations rather than iterating over the entire nums array.

Edge cases include scenarios where all numbers are negative, all multipliers are negative, or m equals n, which forces us to use all numbers. These cases can trip up naive greedy algorithms, because picking the largest immediate product may not yield a globally optimal score.

Approaches

Brute Force Approach

A brute-force approach would try every possible sequence of choices from the start or end for each multiplier. For each operation, we have two options: pick the leftmost or rightmost number. This results in a decision tree with 2^m possible paths, which is computationally infeasible for m = 300, since 2^300 is astronomically large.

Optimal Approach - Dynamic Programming

The key observation is that at each step, the problem exhibits overlapping subproblems and an optimal substructure. The score depends on the number of elements picked from the start versus the end. If we define a DP state dp[i][left] as the maximum score using the first i multipliers and picking left elements from the start, then the remaining elements come from the end. The recurrence is:

dp[i][left] = max(
    dp[i-1][left-1] + multipliers[i-1] * nums[left-1],   # pick from start
    dp[i-1][left] + multipliers[i-1] * nums[n-(i-left)]   # pick from end
)

This reduces the complexity from exponential to O(m^2) time and O(m^2) space, which is feasible given m <= 300. We can further optimize space to O(m) by using a 1D DP array because each step only depends on the previous step.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^m) O(m) Explore all possible sequences of picks
Optimal O(m^2) O(m) Dynamic Programming with rolling array to reduce space

Algorithm Walkthrough

  1. Initialize a DP array dp of size m+1 with all zeros. dp[left] will store the maximum score using the first i multipliers and left picks from the start.
  2. Iterate through the multipliers array from the first multiplier to the last. At step i, calculate the next state next_dp using the current dp values.
  3. For each possible number of left picks left from 0 to i:
  • If we pick from the start, add multipliers[i] * nums[left] to dp[left-1].
  • If we pick from the end, add multipliers[i] * nums[n - 1 - (i - left)] to dp[left].
  • Take the maximum of the two options as the new next_dp[left].
  1. After processing all multipliers, the maximum value in dp represents the optimal score.

Why it works: The DP state correctly tracks the maximum score for all combinations of picks from the start. Because each multiplier is used exactly once, and we explore both options at each step, the recurrence guarantees the global maximum is found.

Python Solution

from typing import List

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n = len(nums)
        m = len(multipliers)
        dp = [0] * (m + 1)
        
        for i in range(1, m + 1):
            next_dp = dp[:]
            multiplier = multipliers[i - 1]
            for left in range(i, -1, -1):
                if left > 0:
                    next_dp[left] = max(next_dp[left], dp[left - 1] + multiplier * nums[left - 1])
                if i - left > 0:
                    next_dp[left] = max(next_dp[left], dp[left] + multiplier * nums[n - (i - left)])
            dp = next_dp
        return max(dp)

This implementation initializes a DP array and iteratively updates it using a rolling approach to avoid O(m^2) space. At each step, it considers both options of picking from the start or end, ensuring the optimal score is maintained.

Go Solution

func maximumScore(nums []int, multipliers []int) int {
    n := len(nums)
    m := len(multipliers)
    dp := make([]int, m+1)

    for i := 1; i <= m; i++ {
        nextDp := make([]int, m+1)
        copy(nextDp, dp)
        multiplier := multipliers[i-1]
        for left := i; left >= 0; left-- {
            if left > 0 {
                val := dp[left-1] + multiplier*nums[left-1]
                if val > nextDp[left] {
                    nextDp[left] = val
                }
            }
            if i-left > 0 {
                val := dp[left] + multiplier*nums[n-(i-left)]
                if val > nextDp[left] {
                    nextDp[left] = val
                }
            }
        }
        dp = nextDp
    }
    maxScore := dp[0]
    for _, val := range dp {
        if val > maxScore {
            maxScore = val
        }
    }
    return maxScore
}

In Go, we handle slices instead of arrays and ensure the rolling DP array is copied correctly. Integer overflow is not an issue since the constraints guarantee the numbers are within reasonable bounds.

Worked Examples

Example 1

nums = [1,2,3], multipliers = [3,2,1]

Step by step:

i left pick from start pick from end dp
1 1 3*1 = 3 - 3
1 0 - 3*3 = 9 9
2 2 prev+2*2 = 7 - 7
2 1 prev+2*1=5 prev+2*2=13 13
2 0 - prev+2*3=11 11
3 ... final max = 14 14

Example 2

nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]

Following similar DP updates yields 102 as the final maximum score.

Complexity Analysis

Measure Complexity Explanation
Time O(m^2) Each of the m multipliers loops through 0..m left picks
Space O(m) Only one rolling DP array of size m+1 is needed

This is efficient given m <= 300, which makes O(m^2) = O(90,000) feasible.

Test Cases

# Basic examples
assert Solution().maximumScore([1,2,3], [3,2,1]) == 14  # example 1
assert Solution().maximumScore([-5,-3,-3,-2,7,1], [-10,-5,3,4,6]) == 102  # example 2

# Edge cases
assert Solution().maximumScore([1], [1]) == 1  # single element
assert Solution().maximumScore([0,0,0], [1,2,3]) == 0  # all zeros
assert Solution().maximumScore([1,-1,1,-1], [1,2,3,4]) == 7  # mix positive/negative

# Stress test with negative multipliers
assert Solution().maximumScore([100,-100,200,-200], [-1,-2,-3,-4]) == 1100
Test Why
[1,2,3], [3,2,1] basic example, simple ascending numbers
[-5,-3,-3,-2,7,1], [-10,-5,3,4,6] mix of positive and negative numbers, multiple operations