 # 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, , 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 =  * (len(mul) + 1)
for m in range(len(mul) - 1, -1, -1):
pd =  * (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``````

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;
}
}``````

### 3 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.