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;
    }
}
Facebook
Twitter
LinkedIn

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

  1. 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!

    Reply
  2. 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.

    Reply

Leave a Comment

%d bloggers like this: