Maximum Score from Performing Multiplication Operations
Hard
#1620Time: 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`.
You are given two 0-indexed integer arrays nums and multipliersof size n and m respectively, where n >= m.
You begin with a score of 0. You want to perform exactlym operations. On the ith operation (0-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.
Note that multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.
Remove x from nums.
Return the maximum score after performing moperations.
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.length
m == multipliers.length
1 <= m <= 300
m <= 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).
Return the maximum of scoreLeft and scoreRight.
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 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.
1class Solution {2 public int maximumScore(int[] nums, int[] multipliers) {3 return solve(0, 0, nums, multipliers);4 }56 private int solve(int i, int left, int[] nums, int[] multipliers) {7 // Base case: all multipliers have been used.8 if (i == multipliers.length) {9 return 0;10 }1112 int n = nums.length;13 // The number of elements taken from the right is i - left.14 // So the right pointer is at n - 1 - (i - left).15 int right = n - 1 - (i - left);1617 // Option 1: Choose the left element18 int pickLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1, nums, multipliers);1920 // Option 2: Choose the right element21 int pickRight = multipliers[i] * nums[right] + solve(i + 1, left, nums, multipliers);2223 return Math.max(pickLeft, pickRight);24 }25}
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.
The brute-force recursive approach suffers from re-calculating the same subproblems. We can optimize this by storing the results of each subproblem (i, left) in a cache or memoization table. When the function is called with the same arguments again, we can directly return the stored result instead of re-computing it.
Algorithm
Create a 2D array memo of size m x m to store results. Initialize it with a value indicating 'not computed' (e.g., using Integer wrapper class and null).
Define a recursive function solve(i, left).
Base Case: If i == m, return 0.
Memoization Check: If memo[i][left] is not null, return the stored value.
Recursive Step: Calculate scores for picking left and right, same as the brute-force approach.
Store Result: Before returning, store the computed maximum score in memo[i][left].
The main function initializes the memo table and calls solve(0, 0).
Walkthrough
We use a 2D array, memo[m][m], to store the results of solve(i, left). The state (i, left) represents using the i-th multiplier and having taken left elements from the start. The number of elements taken from the left, left, can be at most i. So the state space for left is 0...i. The total number of unique states is O(m^2).
Before computing the result for solve(i, left), we first check if it's already in our memo table. If it is, we return the value. Otherwise, we compute it, store it in the table, and then return it. This technique is called memoization, a form of top-down dynamic programming.
1class Solution {2 private int n, m;3 private int[] nums, multipliers;4 private Integer[][] memo;56 public int maximumScore(int[] nums, int[] multipliers) {7 this.n = nums.length;8 this.m = multipliers.length;9 this.nums = nums;10 this.multipliers = multipliers;11 this.memo = new Integer[m][m];12 return solve(0, 0);13 }1415 private int solve(int i, int left) {16 if (i == m) {17 return 0;18 }19 if (memo[i][left] != null) {20 return memo[i][left];21 }2223 int right = n - 1 - (i - left);2425 int pickLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1);26 int pickRight = multipliers[i] * nums[right] + solve(i + 1, left);2728 return memo[i][left] = Math.max(pickLeft, pickRight);29 }30}
Complexity
Time
O(m^2) - There are `O(m^2)` possible states for `(i, left)`, where `0 <= i < m` and `0 <= left <= i`. Each state is computed only once.
Space
O(m^2) - We use a 2D array of size `m x m` for the memoization table. The recursion stack adds an additional `O(m)` space.
Trade-offs
Pros
Drastically improves performance over brute-force by eliminating redundant computations.
Guaranteed to find the optimal solution within the time limits for the given constraints.
Often intuitive to implement by adding a cache to a recursive solution.
Cons
Requires O(m^2) space, which might be substantial if m were much larger.
This approach is an iterative version of the memoized recursion, known as tabulation or bottom-up dynamic programming. Instead of starting from the top state (0, 0) and going down, we start from the base cases and build our way up to the solution. We use a 2D DP table, dp[i][left], to store the maximum score.
Algorithm
Create a 2D DP table dp of size (m + 1) x (m + 1).
The base cases dp[m][left] = 0 for all left are implicitly handled by Java's default array initialization.
Iterate i from m - 1 down to 0.
Inside this loop, iterate left from i down to 0.
Calculate the right index: right = n - 1 - (i - left).
Let dp[i][left] be the maximum score obtainable from the remaining m-i operations (from operation i to m-1), given that left elements have already been taken from the start of nums. The state transition remains the same as in the recursive approach. Since the calculation for dp[i] depends on values from dp[i+1], we must fill the table in decreasing order of i, from m-1 down to 0.
The base cases are dp[m][left] = 0 for all left, as no more operations are left and thus no more score can be gained. The final answer we are looking for is dp[0][0], which represents the maximum score starting from operation 0 with 0 elements taken from the left.
1class Solution {2 public int maximumScore(int[] nums, int[] multipliers) {3 int n = nums.length;4 int m = multipliers.length;5 int[][] dp = new int[m + 1][m + 1];67 for (int i = m - 1; i >= 0; i--) {8 for (int left = i; left >= 0; left--) {9 int right = n - 1 - (i - left);10 int pickLeft = multipliers[i] * nums[left] + dp[i + 1][left + 1];11 int pickRight = multipliers[i] * nums[right] + dp[i + 1][left];12 dp[i][left] = Math.max(pickLeft, pickRight);13 }14 }1516 return dp[0][0];17 }18}
Complexity
Time
O(m^2) - We iterate through the relevant parts of the DP table using two nested loops, each running up to `m` times.
Space
O(m^2) - A 2D array of size `(m + 1) x (m + 1)` is used to store the DP states.
Trade-offs
Pros
Avoids recursion overhead, which can lead to a slight performance improvement over memoization.
Provides a systematic, iterative way to build the solution from the ground up.
Cons
Requires O(m^2) space, same as the memoization approach.
Can sometimes be less intuitive to formulate the iteration order compared to memoization.
This is the most efficient approach in terms of memory. By observing the state transition in the bottom-up DP, we notice that to compute the values for row i of our dp table, we only need the values from the immediately following row, i+1. This allows us to optimize the space complexity from O(m^2) to O(m) by using only a 1D array to store the necessary previous state.
Algorithm
Create a 1D array dp of size m + 1. This will hold the results for a given row i+1.
Iterate i from m - 1 down to 0.
Inside the loop, create a new temporary array next_dp of size m + 1 to store results for row i.
Iterate left from i down to 0.
Calculate the score for picking the left element: multipliers[i] * nums[left] + dp[left + 1].
Calculate the score for picking the right element: multipliers[i] * nums[n - 1 - (i - left)] + dp[left].
Store the maximum of these two scores in next_dp[left].
After the inner loop, update dp to be next_dp for the next iteration.
The final answer is dp[0].
Walkthrough
Instead of a full 2D table, we can maintain a 1D array, dp, of size m+1. This array will represent the (i+1)-th row of the 2D DP table as we compute the i-th row. We iterate i from m-1 down to 0. In each iteration, we compute the values for the current row i based on the values from the previous iteration (which represent row i+1). A second temporary array, next_dp, is used to store the newly computed values for row i to avoid overwriting the values of row i+1 that are still needed. After computing all values for row i, we replace the old dp array with next_dp.
1class Solution {2 public int maximumScore(int[] nums, int[] multipliers) {3 int n = nums.length;4 int m = multipliers.length;5 int[] dp = new int[m + 1];67 for (int i = m - 1; i >= 0; i--) {8 // A new array to store the results for the current row `i`.9 // This could also be called `currentRow` or `dp_i`.10 int[] next_dp = new int[m + 1];11 for (int left = i; left >= 0; left--) {12 int right = n - 1 - (i - left);1314 // Use the `dp` array (which holds results for row i+1) to calculate results for row i.15 int pickLeft = multipliers[i] * nums[left] + dp[left + 1];16 int pickRight = multipliers[i] * nums[right] + dp[left];1718 next_dp[left] = Math.max(pickLeft, pickRight);19 }20 // The results for row `i` now become the 'previous' results for the next iteration (i-1).21 dp = next_dp;22 }2324 return dp[0];25 }26}
Complexity
Time
O(m^2) - The time complexity remains the same as the standard bottom-up DP, with two nested loops.
Space
O(m) - We use two arrays of size `m+1` to store the DP states for the current and previous rows.
Trade-offs
Pros
Most efficient solution in terms of space complexity.
Maintains the optimal O(m^2) time complexity while significantly reducing memory usage.
Cons
The logic for space optimization can be slightly more complex to derive and implement correctly compared to the 2D DP table approach.
Solutions
Solution
1class Solution {2private3 Integer[][] f;4private5 int[] multipliers;6private7 int[] nums;8private9 int n;10private11 int m;12public13 int maximumScore(int[] nums, int[] multipliers) {14 n = nums.length;15 m = multipliers.length;16 f = new Integer[m][m];17 this.nums = nums;18 this.multipliers = multipliers;19 return dfs(0, 0);20 }21private22 int dfs(int i, int j) {23 if (i >= m || j >= m || (i + j) >= m) {24 return 0;25 }26 if (f[i][j] != null) {27 return f[i][j];28 }29 int k = i + j;30 int a = dfs(i + 1, j) + nums[i] * multipliers[k];31 int b = dfs(i, j + 1) + nums[n - 1 - j] * multipliers[k];32 f[i][j] = Math.max(a, b);33 return f[i][j];34 }35}
1class Solution {2public:3 int maximumScore(vector<int> &nums, vector<int> &multipliers) {4 int n = nums.size(), m = multipliers.size();5 int f[m][m];6 memset(f, 0x3f, sizeof f);7 function<int(int, int)> dfs = [&](int i, int j) -> int {8 if (i >= m || j >= m || (i + j) >= m)9 return 0;10 if (f[i][j] != 0x3f3f3f3f)11 return f[i][j];12 int k = i + j;13 int a = dfs(i + 1, j) + nums[i] * multipliers[k];14 int b = dfs(i, j + 1) + nums[n - j - 1] * multipliers[k];15 return f[i][j] = max(a, b);16 };17 return dfs(0, 0);18 }19};
1class Solution:2 def maximumScore(self, nums: List[int], multipliers: List[int]) -> int: @ cache def f(i, j, k): if k >= m or i >= n or j < 0: return 0 a = f(i + 1, j, k + 1) + nums[i] * multipliers[k] b = f(i, j - 1, k + 1) + nums[j] * multipliers[k] return max(a, b) n = len(nums) m = len(multipliers) return f(0, n - 1, 0)
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.
