1770. Maximum Score from Performing Multiplication Operations LeetCode Solution

In this guide, you will get 1770. Maximum Score from Performing Multiplication Operations LeetCode Solution with the best time and space complexity. The solution to Maximum Score from Performing Multiplication Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Score from Performing Multiplication Operations solution in C++
4. Maximum Score from Performing Multiplication Operations solution in Java
5. Maximum Score from Performing Multiplication Operations solution in Python
6. Additional Resources

Problem Statement of Maximum Score from Performing Multiplication Operations

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

Complexity Analysis

• Time Complexity: O(m^2)
• Space Complexity: O(m^2)

1770. Maximum Score from Performing Multiplication Operations LeetCode Solution in C++

class Solution {
 public:
  int maximumScore(vector<int>& nums, vector<int>& multipliers) {
    vector<vector<int>> mem(multipliers.size(),
                            vector<int>(multipliers.size(), -1));
    return maximumScore(nums, 0, multipliers, 0, mem);
  }

 private:
  // Returns the maximum score of nums[s..e] and multipliers[i].
  int maximumScore(const vector<int>& nums, int s,
                   const vector<int>& multipliers, int i,
                   vector<vector<int>>& mem) {
    if (i == multipliers.size())
      return 0;
    if (mem[s][i] != -1)
      return mem[s][i];

    // The number of nums picked on the start side is s.
    // The number of nums picked on the end side is i - s.
    // So, e = n - (i - s) - 1.
    const int e = nums.size() - (i - s) - 1;
    const int pickStart = nums[s] * multipliers[i] +
                          maximumScore(nums, s + 1, multipliers, i + 1, mem);
    const int pickEnd = nums[e] * multipliers[i] +
                        maximumScore(nums, s, multipliers, i + 1, mem);
    return mem[s][i] = max(pickStart, pickEnd);
  }
};
/* code provided by PROGIEZ */

1770. Maximum Score from Performing Multiplication Operations LeetCode Solution in Java

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

  private int maximumScore(int[] nums, int s, int[] multipliers, int i, Integer[][] mem) {
    if (i == multipliers.length)
      return 0;
    if (mem[s][i] != null)
      return mem[s][i];

    // The number of nums picked on the start side is s.
    // The number of nums picked on the end side is i - s.
    // So, e = n - (i - s) - 1.
    final int e = nums.length - (i - s) - 1;
    final int pickStart = nums[s] * multipliers[i] + //
                          maximumScore(nums, s + 1, multipliers, i + 1, mem);
    final int pickEnd = nums[e] * multipliers[i] + //
                        maximumScore(nums, s, multipliers, i + 1, mem);
    return mem[s][i] = Math.max(pickStart, pickEnd);
  }
}
// code provided by PROGIEZ

1770. Maximum Score from Performing Multiplication Operations LeetCode Solution in Python

class Solution:
  def maximumScore(self, nums: list[int], multipliers: list[int]) -> int:
    @functools.lru_cache(2000)
    def dp(s: int, i: int) -> int:
      """Returns the maximum score of nums[s..e] and multipliers[i]."""
      if i == len(multipliers):
        return 0

      # The number of nums picked on the start side is s.
      # The number of nums picked on the end side is i - s.
      # So, e = n - (i - s) - 1.
      e = len(nums) - (i - s) - 1
      pickStart = nums[s] * multipliers[i] + dp(s + 1, i + 1)
      pickEnd = nums[e] * multipliers[i] + dp(s, i + 1)
      return max(pickStart, pickEnd)

    return dp(0, 0)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.