Watch 10 video solutions for Maximum Score from Performing Multiplication Operations, a hard level problem involving Array, Dynamic Programming. This walkthrough by Fraz has 11,357 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |