Maximum Score from Performing Multiplication Operations solution and explanation
Google
9 more videos on this problem
Leetcode 1770. Maximum Score from Performing Multiplication OperationsFraz · 18:50 · 11K views
花花酱 LeetCode 1770. Maximum Score from Performing Multiplication Operations - 刷题找工作 EP385Hua Hua · 19:26 · 2K views
LeetCode 1770. Maximum Score from Performing Multiplication Operations | Visualization | PythonAH Tech · 6:31 · 2K views
LeetCode 1770. Maximum Score from Performing Multiplication Operations | Weekly Contest 229 | C++Cherry Coding [IIT-G] · 10:21 · 2K views
Leetcode 1770 Maximum Score from Performing Multiplication Operations | DP Coding Decoded SDE SheetCoding Decoded · 12:00 · 2K views
1770. Maximum Score from Performing Multiplication Operations (Leetcode Medium)Programming Live with Larry · 42:00 · 943 views
Daily Leetcode #899: Sep 16, 2022 - 1770. Maximum Score from Performing Multiplication ..Programming Live with Larry · 37:13 · 812 views
1770. Maximum Score from Performing Multiplication Operations || DSA || Leetcode Daily ChallengeLeetcode Daily Challenge · 9:08 · 750 views
Leetcode 1770 Maximum Score Performing Multiplication Operations | HindiThinkCode · 14:41 · 743 views
DP-10 | 1770. Maximum Score from Performing Multiplication Operations (Part - 1) | #10 | DP PlaylistCTO Bhaiya · 37:30 · 537 views
The problem
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
Approach overview
Problem 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 1: Dynamic Programming Approach
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.
def maximum_score(nums, multipliers):
n, m = len(nums), len(multipliers)
dp = [[0] * (m + 1) for _ in range(m + 1)]
for i in range(m - 1, -1, -1):
for left in range(i, -1, -1):
pick_start = multipliers[i] * nums[left] + dp[i + 1][left + 1]
pick_end = multipliers[i] * nums[n - 1 - (i - left)] + dp[i + 1][left]
dp[i][left] = max(pick_start, pick_end)
return dp[0][0]class Solution {
public int maximumScore(int[] nums, int[] multipliers) {
int n = nums.length, m = multipliers.length;
int[][] dp = new int[m + 1][m + 1];
for (int i = m - 1; i >= 0; i--) {
for (int left = i; left >= 0; left--) {
dp[i][left] = Math.max(
multipliers[i] * nums[left] + dp[i + 1][left + 1],
multipliers[i] * nums[n - 1 - (i - left)] + dp[i + 1][left]
);
}
}
return dp[0][0];
}
}#include<vector>
#include<algorithm>
using namespace std;
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int n = nums.size(), m = multipliers.size();
vector<vector<int>> dp(m + 1, vector<int>(m + 1, 0));
for (int i = m - 1; i >= 0; --i) {
for (int left = i; left >= 0; --left) {
dp[i][left] = max(
multipliers[i] * nums[left] + dp[i + 1][left + 1],
multipliers[i] * nums[n - 1 - (i - left)] + dp[i + 1][left]
);
}
}
return dp[0][0];
}function maximumScore(nums, multipliers) {
let n = nums.length, m = multipliers.length;
let dp = Array.from({length: m + 1}, () => Array(m + 1).fill(0));
for (let i = m - 1; i >= 0; --i) {
for (let left = i; left >= 0; --left) {
dp[i][left] = Math.max(
multipliers[i] * nums[left] + dp[i + 1][left + 1],
multipliers[i] * nums[n - 1 - (i - left)] + dp[i + 1][left]
);
}
}
return dp[0][0];
}#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) { return a > b ? a : b; }
int maximumScore(int* nums, int numsSize, int* multipliers, int multipliersSize) {
int m = multipliersSize;
int** dp = (int**)malloc((m + 1) * sizeof(int*));
for (int i = 0; i <= m; ++i) dp[i] = (int*)calloc((m + 1), sizeof(int));
for (int i = m - 1; i >= 0; --i) {
for (int left = i; left >= 0; --left) {
dp[i][left] = max(
multipliers[i] * nums[left] + dp[i + 1][left + 1],
multipliers[i] * nums[numsSize - 1 - (i - left)] + dp[i + 1][left]
);
}
}
int result = dp[0][0];
for (int i = 0; i <= m; ++i) free(dp[i]);
free(dp);
return result;
}using System;
public class Solution {
public int MaximumScore(int[] nums, int[] multipliers) {
int n = nums.Length, m = multipliers.Length;
int[,] dp = new int[m + 1, m + 1];
for (int i = m - 1; i >= 0; i--) {
for (int left = i; left >= 0; left--) {
dp[i, left] = Math.Max(
multipliers[i] * nums[left] + dp[i + 1, left + 1],
multipliers[i] * nums[n - 1 - (i - left)] + dp[i + 1, left]
);
}
}
return dp[0, 0];
}
}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.
Approach 2: Greedy Approach
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.
def maximum_score(nums, multipliers):
left, right = 0, len(nums) - 1
score = 0
for multiplier in multipliers:
if multiplier * nums[left] >= multiplier * nums[right]:
score += multiplier * nums[left]
left += 1
else:
score += multiplier * nums[right]
right -= 1
return scoreclass Solution {
public int maximumScore(int[] nums, int[] multipliers) {
int left = 0, right = nums.length - 1;
int score = 0;
for (int multiplier : multipliers) {
if (multiplier * nums[left] >= multiplier * nums[right]) {
score += multiplier * nums[left++];
} else {
score += multiplier * nums[right--];
}
}
return score;
}
}#include<vector>
#include<algorithm>
using namespace std;
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int left = 0, right = nums.size() - 1;
int score = 0;
for (int multiplier : multipliers) {
if (multiplier * nums[left] >= multiplier * nums[right]) {
score += multiplier * nums[left++];
} else {
score += multiplier * nums[right--];
}
}
return score;
}function maximumScore(nums, multipliers) {
let left = 0, right = nums.length - 1;
let score = 0;
for (let multiplier of multipliers) {
if (multiplier * nums[left] >= multiplier * nums[right]) {
score += multiplier * nums[left];
left += 1;
} else {
score += multiplier * nums[right];
right -= 1;
}
}
return score;
}#include <stdio.h>
int maximumScore(int* nums, int numsSize, int* multipliers, int multipliersSize) {
int left = 0, right = numsSize - 1;
int score = 0;
for (int i = 0; i < multipliersSize; ++i) {
if (multipliers[i] * nums[left] >= multipliers[i] * nums[right]) {
score += multipliers[i] * nums[left++];
} else {
score += multipliers[i] * nums[right--];
}
}
return score;
}public class Solution {
public int MaximumScore(int[] nums, int[] multipliers) {
int left = 0, right = nums.Length - 1;
int score = 0;
foreach (int multiplier in multipliers) {
if (multiplier * nums[left] >= multiplier * nums[right]) {
score += multiplier * nums[left++];
} else {
score += multiplier * nums[right--];
}
}
return score;
}
}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.
Approach 3: Default Approach
function maximumScore(nums: number[], multipliers: number[]): number {
const inf = 1 << 30;
const n = nums.length;
const m = multipliers.length;
const f = new Array(m + 1).fill(0).map(() => new Array(m + 1).fill(-inf));
f[0][0] = 0;
let ans = -inf;
for (let i = 0; i <= m; ++i) {
for (let j = 0; j <= m - i; ++j) {
const k = i + j - 1;
if (i > 0) {
f[i][j] = Math.max(f[i][j], f[i - 1][j] + nums[i - 1] * multipliers[k]);
}
if (j > 0) {
f[i][j] = Math.max(f[i][j], f[i][j - 1] + nums[n - j] * multipliers[k]);
}
if (i + j === m) {
ans = Math.max(ans, f[i][j]);
}
}
}
return ans;
}func maximumScore(nums []int, multipliers []int) int {
n, m := len(nums), len(multipliers)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, m)
for j := range f[i] {
f[i][j] = 1 << 30
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= m || j >= m || i+j >= m {
return 0
}
if f[i][j] != 1<<30 {
return f[i][j]
}
k := i + j
a := dfs(i+1, j) + nums[i]*multipliers[k]
b := dfs(i, j+1) + nums[n-j-1]*multipliers[k]
f[i][j] = max(a, b)
return f[i][j]
}
return dfs(0, 0)
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Score from Performing Multiplication Operations easy or hard?
The problem is rated Hard because greedy intuition alone fails and the correct solution requires defining a non‑obvious DP state. Candidates must reason about how left and right picks affect the remaining array and design an O(m^2) dynamic programming solution.
How to solve Maximum Score from Performing Multiplication Operations in O(m^2)?
Define dp[i][l] as the maximum score after performing i operations and taking l numbers from the left. The right index becomes n - 1 - (i - l). For each state, compute the maximum between picking from the left or the right using the current multiplier. Filling all states results in an O(m^2) dynamic programming solution.
Maximum Score from Performing Multiplication Operations Python or Java solution?
The solution is typically implemented using dynamic programming with memoization or bottom-up tabulation. Python often uses recursion with functools.lru_cache, while Java implementations commonly use a 2D DP array or optimized 1D rolling array.
What is the best approach for Maximum Score from Performing Multiplication Operations?
Dynamic Programming is the optimal approach. Track the number of operations performed and how many elements were taken from the left side of the array. This state determines the remaining right index and allows computing the maximum score through two choices. The overall complexity is O(m^2) time where m is the number of multipliers.
Is Maximum Score from Performing Multiplication Operations asked at Google/Amazon/Meta?
This problem follows a classic dynamic programming pattern involving decisions from both ends of an array. Variations of this pattern appear in interviews at companies such as Google, Amazon, and Meta because they test state modeling, DP transitions, and optimization of overlapping subproblems.
What data structure is used in Maximum Score from Performing Multiplication Operations?
The core structure is a dynamic programming table or memoization cache. It stores intermediate results for states defined by the number of operations performed and the number of elements taken from the left side of the array.
What is the time complexity of Maximum Score from Performing Multiplication Operations?
The optimal dynamic programming solution runs in O(m^2) time and O(m^2) space, where m is the number of multipliers. Each DP state represents a pair (operations performed, elements taken from the left). Since there are roughly m * m states and each transition takes constant time, the total complexity becomes quadratic in m.