Maximum Score from Performing Multiplication Operations
Problem
Given arrays nums and multipliers, on step i pick either nums[front] or nums[back], multiply by multipliers[i], add to score, and remove that element. Maximize total score.
nums = [1,2,3], multipliers = [3,2,1]14def maximum_score(nums, multipliers):
m = len(multipliers)
n = len(nums)
dp = [[0] * (m + 1) for _ in range(m + 1)]
for i in range(m - 1, -1, -1):
for left in range(i, -1, -1):
right = n - 1 - (i - left)
dp[i][left] = max(
nums[left] * multipliers[i] + dp[i+1][left+1],
nums[right] * multipliers[i] + dp[i+1][left]
)
return dp[0][0]function maximumScore(nums, multipliers) {
const m = multipliers.length, n = nums.length;
const dp = Array.from({length: m + 1}, () => new Array(m + 1).fill(0));
for (let i = m - 1; i >= 0; i--) {
for (let left = i; left >= 0; left--) {
const right = n - 1 - (i - left);
dp[i][left] = Math.max(
nums[left] * multipliers[i] + dp[i+1][left+1],
nums[right] * multipliers[i] + dp[i+1][left]
);
}
}
return dp[0][0];
}class Solution {
public int maximumScore(int[] nums, int[] multipliers) {
int m = multipliers.length, n = nums.length;
int[][] dp = new int[m + 1][m + 1];
for (int i = m - 1; i >= 0; i--) {
for (int left = i; left >= 0; left--) {
int right = n - 1 - (i - left);
dp[i][left] = Math.max(
nums[left] * multipliers[i] + dp[i+1][left+1],
nums[right] * multipliers[i] + dp[i+1][left]
);
}
}
return dp[0][0];
}
}int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int m = multipliers.size(), n = nums.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--) {
int right = n - 1 - (i - left);
dp[i][left] = max(
nums[left] * multipliers[i] + dp[i+1][left+1],
nums[right] * multipliers[i] + dp[i+1][left]
);
}
}
return dp[0][0];
}Explanation
On each of the m steps you pick a number from either the front or the back of nums, multiply it by the matching multiplier, and add it to your score. The key insight is that the state can be described by just two numbers: how many steps you've done, and how many of those came from the front.
We define dp[i][left] as the best score you can still earn starting from step i when you've already taken left numbers from the front. Knowing i and left, the back pointer is forced: right = n - 1 - (i - left).
At each state we try both moves and keep the bigger: take nums[left] * multipliers[i] and recurse with one more front pick, or take nums[right] * multipliers[i] and recurse with the back. We fill the table backwards so the future values are ready.
Example: nums = [1,2,3], multipliers = [3,2,1]. The best sequence multiplies the right numbers by the big early multipliers, reaching a total of 14, which the table reports at dp[0][0].
There are only about m²/2 useful states and each is decided in constant time, so the algorithm is O(m²).