Maximum Score from Performing Multiplication Operations
HardPrompt
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:
- Choose one integer
xfrom either the start or the end of the arraynums. - Add
multipliers[i] * xto your score.- Note that
multipliers[0]corresponds to the first operation,multipliers[1]to the second operation, and so on.
- Note that
- Remove
xfromnums.
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] <= 1000
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's choices into a recursive function. At each step i (from 0 to m-1), we have two choices: pick the leftmost available element or the rightmost available element from the nums array. We explore both paths recursively and return the maximum score obtained.
Algorithm
- Define a recursive function
solve(i, left, nums, multipliers). - Base Case: If
i == multipliers.length, it means all multipliers have been used, so return 0. - Calculate the index of the rightmost available element:
right = n - 1 - (i - left). - Recursive Step: Explore both choices:
- Pick from the left:
scoreLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1, nums, multipliers). - Pick from the right:
scoreRight = multipliers[i] * nums[right] + solve(i + 1, left, nums, multipliers).
- Pick from the left:
- Return the maximum of
scoreLeftandscoreRight. - The initial call from the main function is
solve(0, 0, nums, multipliers).
Walkthrough
We define a recursive helper function, say solve(i, left), which calculates the maximum score we can get from the i-th operation onwards, given that we have already picked left elements from the start of the original nums array.
- The number of operations performed so far is
i. - The number of elements picked from the left is
left. - Therefore, the number of elements picked from the right is
i - left. - The next available element from the left is at index
left. - The next available element from the right is at index
n - 1 - (i - left).
The recursive formula is:
solve(i, left) = max( (multipliers[i] * nums[left]) + solve(i + 1, left + 1), (multipliers[i] * nums[n - 1 - (i - left)]) + solve(i + 1, left) )
The base case for the recursion is when i == m, meaning all multipliers have been used. In this case, the score from this point onwards is 0.
class Solution { public int maximumScore(int[] nums, int[] multipliers) { return solve(0, 0, nums, multipliers); } private int solve(int i, int left, int[] nums, int[] multipliers) { // Base case: all multipliers have been used. if (i == multipliers.length) { return 0; } int n = nums.length; // The number of elements taken from the right is i - left. // So the right pointer is at n - 1 - (i - left). int right = n - 1 - (i - left); // Option 1: Choose the left element int pickLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1, nums, multipliers); // Option 2: Choose the right element int pickRight = multipliers[i] * nums[right] + solve(i + 1, left, nums, multipliers); return Math.max(pickLeft, pickRight); }}Complexity
Time
O(2^m) - For each of the `m` multipliers, the function branches into two recursive calls. This creates a binary recursion tree of depth `m`, leading to an exponential number of operations.
Space
O(m) - The space complexity is determined by the maximum depth of the recursion stack, which is `m`.
Trade-offs
Pros
Simple to understand and implement as it directly models the decision-making process.
Cons
Extremely inefficient due to an exponential number of redundant calculations.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution {private Integer[][] f;private int[] multipliers;private int[] nums;private int n;private int m;public int maximumScore(int[] nums, int[] multipliers) { n = nums.length; m = multipliers.length; f = new Integer[m][m]; this.nums = nums; this.multipliers = multipliers; return dfs(0, 0); }private int dfs(int i, int j) { if (i >= m || j >= m || (i + j) >= m) { return 0; } if (f[i][j] != null) { return f[i][j]; } int k = i + j; int a = dfs(i + 1, j) + nums[i] * multipliers[k]; int b = dfs(i, j + 1) + nums[n - 1 - j] * multipliers[k]; f[i][j] = Math.max(a, b); return f[i][j]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.