Maximum Score From Performing Multiplication Operations - Leetcode Solution

Problem Description:

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

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

Choose one integer nums[j] and one integer multipliers[i]. Multiply multipliers[i] by nums[j]. Add the result to your score. Remove multipliers[i] and nums[j] from their respective arrays.

Return the maximum score after performing m operations.

Solution:

To find the maximum score after performing m operations, we need to generate all possible sequences of length m, where each sequence has m pairs of indices (x, y), where x is in the range [1, n] and y is in the range [1, m]. Each pair represents the indices of the numbers from the two arrays that will be multiplied in the ith operation.

There are 10^6 possible sequences, which is too large to generate them all and check their score. To reduce the search space, we can use dynamic programming to memoize the scores of the subproblems. Let dp[i][j] be the maximum score that can be obtained after performing i operations, using the first j numbers from nums and the first i-j numbers from multipliers. Note that j <= i, because we need j numbers to perform j operations.

To compute dp[i][j], we have two choices:

• Multiply nums[j] with the ith multiplier, add the result to the current score, and recursively call dp[i-1][j-1] to perform the next operation with one fewer number and one fewer multiplier.
• Multiply nums[n] with the ith multiplier, add the result to the current score, and recursively call dp[i-1][j] to perform the next operation with the same number of multipliers but one fewer number.

We take the maximum of these two choices, and return the result. The base case is dp[0][j] = 0, because we can't perform any operations without numbers or multipliers.

The time complexity of this solution is O(m^2), because we need to compute dp[i][j] for O(m^2) subproblems. The space complexity is also O(m^2), because we use a 2D array to store the memoized values. We can optimize the space by using only one row of the dp array at a time, and computing the next row using the current row, but this will not significantly improve the time complexity.

Code:

The following code implements the above solution:

class Solution { public: int maximumScore(vector<int>& nums, vector<int>& multipliers) { int n = nums.size(); int m = multipliers.size(); vector<vector<int>> dp(m+1, vector<int>(m+1, INT_MIN)); dp[0][0] = 0; int score = INT_MIN; for (int i = 1; i <= m; i++) { for (int j = 0; j <= i; j++) { if (j > n || i-j > m) continue; // skip invalid indices if (j > 0) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + nums[j-1] * multipliers[i-1]); if (n-j > 0) dp[i][j] = max(dp[i][j], dp[i-1][j] + nums[n-j] * multipliers[i-1]); if (i == m) score = max(score, dp[i][j]); // update maximum score } } return score; } };

The code uses the following tricks:

• The subproblem dp[i][j] can be computed only if j <= i and j <= n and i-j <= m. If these conditions are not satisfied, the value is invalid and should be skipped.
• The maximum score can be extracted from the last row of the dp array, because it represents the maximum score possible with m operations.

1