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

Que No:4 DSA |Reverse The Array to ...

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:14Explanation:An optimal solution is as follows: - Choose from the end, [1,2,], adding 3 * 3 = 9 to the score. - Choose from the end, [1,3], adding 2 * 2 = 4 to the score. - Choose from the end, [2], adding 1 * 1 = 1 to the score. The total score is 9 + 4 + 1 = 14.1

**Example 2:**

Input:nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]Output:102Explanation: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,-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,-3], adding 1 * 4 = 4 to the score. - Choose from the end, [-2,1], adding 7 * 6 = 42 to the score. The total score is 50 + 15 - 9 + 4 + 42 = 102.7

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”

what does dp mean?

Dynamic Programming

I visted many webssites except thhe audio quality for audio songs existin at this website

iss actually wonderful.

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!

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.

bookmarked!!, I like your web site!