You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m.
You begin with a score of 0. You want to perform exactly m operations. On the ith operation (0-indexed) you will:
x from either the start or the end of the array nums.multipliers[i] * x to your score.
multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.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: An optimal solution is as follows: - Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score. - Choose from the end, [1,2], adding 2 * 2 = 4 to the score. - Choose from the end, [1], adding 1 * 1 = 1 to the score. The total score is 9 + 4 + 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: - Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score. - Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score. - Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score. - Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score. - Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. The total score is 50 + 15 - 9 + 4 + 42 = 102.
Constraints:
n == nums.lengthm == multipliers.length1 <= m <= 300m <= n <= 105 -1000 <= nums[i], multipliers[i] <= 1000Problem Overview: You have an array nums and another array multipliers. For each multiplier, you choose either the leftmost or rightmost value from nums, multiply it with the current multiplier, and add it to the score. The goal is to maximize the final score after performing exactly m operations.
Approach 1: Greedy Choice from Ends (O(m) time, O(1) space)
A straightforward idea is to always pick the larger product between nums[left] * multipliers[i] and nums[right] * multipliers[i]. You maintain two pointers at the start and end of the array and move the pointer corresponding to the chosen value. This runs in O(m) time since each operation makes one decision. The limitation: local decisions do not guarantee a global optimum. A smaller product early might enable a larger combination later, so this approach fails on many cases but helps build intuition for the problem structure.
Approach 2: Dynamic Programming on Picks (O(m²) time, O(m²) space)
The optimal solution uses dynamic programming. At operation i, you have taken some numbers from the left and some from the right. If l numbers were taken from the left, then i - l were taken from the right. This state uniquely determines the remaining subarray. Define dp[i][l] as the maximum score after i operations with l picks from the left.
From this state, you have two choices: take the next number from the left or from the right. The right index can be derived as n - 1 - (i - l). Transition by computing both options and taking the maximum. Because i ranges up to m and l ranges up to m, the total states are O(m²). Each state does constant work, giving O(m²) time complexity. This technique is a classic interval-style DP frequently seen in array and decision problems.
The DP can be implemented with top-down memoization or bottom-up tabulation. Many implementations compress space to O(m) because each step only depends on the next layer.
Recommended for interviews: The dynamic programming approach is what interviewers expect. The greedy strategy shows you recognize the two-end choice pattern, but the DP solution demonstrates that you can model state transitions and optimize overlapping subproblems. Problems combining dynamic programming with array decisions appear frequently in Google, Amazon, and Meta interviews.
This approach involves using dynamic programming to keep track of the maximum scores obtainable by choosing elements from either the start or the end of the nums array during each step of the operations defined by the multipliers array. We maintain a 2D DP table where dp[i][j] represents the maximum score obtained by using the first (i + j) elements from nums, where i elements have been chosen from the start, and j elements have been chosen from the end.
The function maximum_score initializes a 2D array dp with dimensions (m+1) x (m+1). We iterate through the operations and the elements chosen from the start. For each combination of choices, we compute the score achievable by either picking from the start or end. We fill up the DP table backwards, taking the maximum of both potential choices.
Time Complexity: O(m^2), where m is the length of the multipliers array, because we're filling an m x m DP table.
Space Complexity: O(m^2) due to the storage requirements of the m x m DP table.
This approach uses a simpler greedy strategy to try and choose the best possible option at each step, based on examining both the start and end of the nums array for potential scores. It evaluates which element, when multiplied with the current multiplier, gives the maximum increase in the score and selects that iteratively through all operations.
The function computes the maximum playable score using a greedy method that goes through each multiplier in the multipliers array. At each step, it determines whether picking the starting element or the ending element in the nums array yields a better score and then opts for that choice until all operations are exhausted.
Time Complexity: O(m), where m is the number of operations.
Space Complexity: O(1), utilizing constant space regardless of input size.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m^2), where m is the length of the multipliers array, because we're filling an m x m DP table. |
| Greedy Approach | Time Complexity: O(m), where m is the number of operations. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Pick from Ends | O(m) | O(1) | Quick heuristic or intuition building, but not guaranteed optimal |
| Dynamic Programming (State: operations, left picks) | O(m²) | O(m²) or O(m) optimized | General optimal solution for all inputs; standard interview approach |
Leetcode 1770. Maximum Score from Performing Multiplication Operations • Fraz • 11,357 views views
Watch 9 more video solutions →Practice Maximum Score from Performing Multiplication Operations with our built-in code editor and test cases.
Practice on FleetCode