# Leet Code : Maximum Score from Performing Multiplication Operations Cpp | Java | Python solution

Two integer arrays, nums and multipliers, of sizes n and m, respectively, are provided to you, where n >= m. The arrays are all one-dimensional.

You start with a score of zero. You need to carry out precisely m operations. On the ith (1-indexed) action, you will:

Choose one integer x from the beginning or end of the array nums.

Increase your score by multipliers[i] * x.

Take x out of the array nums.

After doing m operations, return the highest possible score.

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.```

Solution :

Python :

DP solution :

`````` dp = [0] * (len(mul) + 1)
for m in range(len(mul) - 1, -1, -1):
pd = [0] * (m + 1)
for l in range(m, -1, -1):
pd[l] = max(dp[l + 1] + mul[m] * nums[l],
dp[l] + mul[m] * nums[~(m - l)])
dp = pd
return dp[0]``````

CPP

DP Solution :

• Instead of initializing DP by 0, initialize it by `INT_MIN`.
• Why ? Because 0 is a valid score.
• As 0 is a valid score, when the `dp[j][i]` is indeed 0, we will recompute the value and thus waste time. We can initialize `dp[j][i]` to INT_MIN instead.
``````class Solution {
public:
vector<vector<int>> dp;

int solve(int i, int n, int j, vector<int> &nums, vector<int> &M){

if (j == M.size()) return 0;
if (dp[i][j] != INT_MIN) return dp[i][j];

// Left Side
int left = solve(i + 1, n, j + 1, nums, M) + (nums[i] * M[j]);

// Right Side
int right = solve(i, n, j + 1, nums, M) + (nums[(n - 1) - (j - i)] * M[j]);

return dp[i][j] = max(left, right);
}

int maximumScore(vector<int>& nums, vector<int>& M) {
int n = nums.size(), m = M.size();
dp.resize(m + 1, vector<int>(m + 1, INT_MIN));
return solve(0, n, 0, nums, M);
}
};``````

Java

``````class Solution {
int N, M;
public int maximumScore(int[] nums, int[] multipliers) {
N = nums.length;
M = multipliers.length;
return helper(nums, multipliers, 0, 0, new Integer[M][M]);
}

private int helper(int[] nums, int[] multipliers, int left, int index, Integer[][] dp) {
int right = N - 1 - (index - left);
if (index == M) return 0;

if (dp[left][index] != null) return dp[left][index];

int res = Math.max(
nums[left] * multipliers[index] + helper(nums, multipliers, left+1, index+1, dp),
nums[right] * multipliers[index] + helper(nums, multipliers, left, index+1, dp));

dp[left][index] = res;
return res;
}
}``````

### 6 thoughts on “Leet Code : Maximum Score from Performing Multiplication Operations Cpp | Java | Python solution”

1. what does dp mean?

• Dynamic Programming

2. I visted many webssites except thhe audio quality for audio songs existin at this website
iss actually wonderful.

3. Have yyou ever tought abvout adding a lttle bit more than jst yourr articles?
I mean, what youu ssay iis important andd everything. Nevertheless jhst imagine if yoou added some great visuals or
vdeo clips to ive yoiur posts more, “pop”! Youur contgent iss excellent butt wifh pihs and
videos, thbis ssite could certaionly be one of the
est inn itts niche. Suplerb blog!

4. Doees your website have a conact page? I’m having probleems
locating it but, I’d lioke too suoot yyou an e-mail.
I’ve goot somme sugghestions for your blokg you mijght bbe intereted iin hearing.
Eituer way, grest webite and I lok forward to seeing itt expand ovver time.

5. bookmarked!!, I like your web site!