1770. Maximum Score from Performing Multiplication Operations

 Maximum Score from Performing Multiplication Operations

Problem Description

You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m.

You begin with a score of 0. You want to perform exactly m operations. On the ith operation (0-indexed) you will:

• Choose one integer x from either the start or the end of the array nums.
• Add multipliers[i] * x to your score.
  • Note that multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.
• Remove x from nums.

Return the maximum score after performing m operations.

 

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.

 

Constraints:

• n == nums.length
• m == multipliers.length
• 1 <= m <= 300
• m <= n <= 105
• -1000 <= nums[i], multipliers[i] <= 1000

A) Recursion

/**
 * @param {number[]} nums
 * @param {number[]} multipliers
 * @return {number}
 */
function recursion(l, i, nums, muls, memo) {
  if (i === muls.length) {
    return 0
  }
  if (memo[l][i] != null) {
    return memo[l][i]
  }

  let left = l
  let right = nums.length - (i - l) - 1
  let case1 = muls[i] * nums[left] + recursion(l + 1, i + 1, nums, muls, memo)
  let case2 = muls[i] * nums[right] + recursion(l, i + 1, nums, muls, memo)
  memo[l][i] = Math.max(case1, case2)

  return memo[l][i]
}

var maximumScore = function(nums, multipliers) {
    let memo = Array.from({ length: multipliers.length }, _ =>
        Array(multipliers.length).fill(null)
    )
    return recursion(0, 0, nums, multipliers, memo)
};

B)Bottom-Up DP Approach

/**
 * @param {number[]} nums
 * @param {number[]} multipliers
 * @return {number}
 */
var maximumScore = function(nums, multipliers) {
  const n = nums.length;
  const m = multipliers.length;
  const best = new Array(m + 1).fill(0).map(() => new Array(m + 1).fill(0));
  
  for (let i = 1; i <= m; i += 1) {
    best[i][0] += best[i-1][0] + nums[n-i] * multipliers[i-1];
    best[0][i] += best[0][i-1] + nums[i-1] * multipliers[i-1];
  }
  
  let max = Math.max(best[m][0], best[0][m]);
  
  
  for (let i = 1; i <= m; i += 1) {
    for (let j = 1; j <= m - i; j += 1) {
      best[i][j] = Math.max(
        best[i-1][j] + nums[n - i] * multipliers[i + j - 1],
        best[i][j-1] + nums[j - 1] * multipliers[i + j - 1],
      );
    }
    max = Math.max(max, best[i][m-i]);
  }
  
  return max;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem#1770. Maximum Score from Performing Multiplication Operations

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve Leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here

Happy coding!