1770. Maximum Score from Performing Multiplication Operations


Problem Description

You are given two arrays nums and multipliers. Array nums is of size n, and multipliers is of size m, with the condition that n >= m. You start with a score of 0 and intend to perform exactly m operations to maximize your score.

Each operation consists of the following steps:

  1. Select an integer x from either the start or end of the array nums.
  2. Multiply x by the corresponding multipliers[i] (where i is the index of the current operation, starting at 0) and add the result to your score.
  3. Remove x from nums.

The challenge is to figure out the sequence of operations that leads to the maximum possible score after performing m operations, and return this maximum score.

Intuition

To solve this problem, we use dynamic programming to keep track of the highest score we can achieve after a certain number of operations. Specifically, we create a 2D array f where f[i][j] represents the maximum score we can achieve by selecting i elements from the start and j elements from the end of nums. The value of k in the code represents the current operation we're on, and ans will store our final answer.

Here's the intuition behind the solution step by step:

  1. We prepare a 2D DP array f with dimensions (m + 1) x (m + 1) where each cell is initially filled with negative infinity (-inf) because we want to calculate the maximum. The +1 ensures we have space for zero selections from both ends.

  2. Set f[0][0] to 0 as the base case, which represents that no operation has been performed yet and the score is zero.

  3. For each possible set of selections from the start and end (represented by i and j respectively), calculate the score for that state and store it in f[i][j].

  4. For the state represented by f[i][j], we consider two possibilities:

    • f[i - 1][j] + multipliers[k] * nums[i - 1]: This corresponds to selecting the element x from the start of the array.
    • f[i][j - 1] + multipliers[k] * nums[n - j]: This corresponds to selecting the element x from the end of the array.
  5. Take the maximum of these two values to find the optimal score for that particular operation.

  6. If the sum of i and j is equal to m (meaning all operations have been used), update ans to track the highest score found up to that point.

  7. After evaluating all possible combinations of selections from nums, return the maximum score ans.

This approach ensures that at every step, we are considering all possible choices and computing the optimal score that can be achieved given the previous decisions, thereby solving the problem optimally.

Solution Approach

The solution approach uses dynamic programming, a method for solving a complex problem by breaking it down into simpler subproblems. It is applicable here because the decision at each step depends on the results of previous steps, and there are overlapping subproblems.

The implementation details are as follows:

  • Initialization: Create a 2D list f of size (m + 1) x (m + 1), where m is the length of the multipliers array, and set all elements to -inf. This represents the maximum possible scores. Additionally, set f[0][0] to 0 as a starting point since no operations mean no score.

  • Nested Loops: Two nested loops iterate over all possibilities where i represents the number of elements selected from the start, and j represents the number of elements selected from the end. Since the problem requires exactly m operations, the outer loop ranges from 0 to m, inclusive, ensuring i + j <= m.

  • State Update: For each (i, j) pair:

    • Calculate the index k = i + j - 1, which represents the operation number.
    • Update f[i][j] according to the dynamic programming state transition equation:
      • If i > 0, meaning we can select from the start, update f[i][j] with the maximum of its current value or the value from choosing the start (f[i - 1][j] + multipliers[k] * nums[i - 1]).
      • If j > 0, meaning we can select from the end, update f[i][j] with the maximum of its current value or the value from choosing the end (f[i][j - 1] + multipliers[k] * nums[n - j]).
    • Check if i + j equals m, that is, if we have performed m operations. If so, update ans with the maximum of its current value and f[i][j].
  • Answer Calculation: After populating the f table with all possible scores, ans, which has been tracking the maximum, will contain the maximum score possible. Hence, return ans.

By storing and updating the maximum score at each state, the solution efficiently computes the maximum score possible after m operations. This dynamic programming table eliminates the need to recompute overlapping subproblems and ensures each subproblem is solved only once. The final answer is found by considering all possible ways to perform the m operations.

Example Walkthrough

Let's illustrate the dynamic programming solution approach with a small example.

Suppose we have:

1nums = [1, 2, 3]
2multipliers = [3, 2]

Here, n = 3 (size of nums) and m = 2 (size of multipliers). As per the problem, we have to perform m operations, so in this case, we need to perform 2 operations.

Following the solution approach:

  1. Initialization: We create a 2D list f with dimensions (3 x 3) (since m + 1 = 2 + 1 = 3), initializing all elements to -inf. Then, set f[0][0] to 0. The table looks like this:
1f = [
2  [0, -inf, -inf],
3  [-inf, -inf, -inf],
4  [-inf, -inf, -inf]
5]
  1. Nested Loops: We iterate through all combinations of i (selections from the start) and j (selections from the end). Our loops will cover (i, j) pairs such as (0, 0), (1, 0), (0, 1), and so on, but will not exceed i + j = m:
1For i = 0 to 2
2    For j = 0 to 2
3        If i + j <= 2 // This is our operation limit `m`
4            Perform state updates
  1. State Update: We update f[i][j] for each (i, j) pair:
    • When i = 1 and j = 0, k = 0:
      • We can take from the start: f[1][0] gets updated to max(-inf, 0 + 3 * nums[0]) which is 3.
    • When i = 0 and j = 1, k = 0:
      • We can take from the end: f[0][1] gets updated to max(-inf, 0 + 3 * nums[2]) which is 9.

We continue doing this to fill out our table f. After the first set of operations, part of our table looks like this:

1f = [
2  [0, 9, -inf],
3  [3, -inf, -inf],
4  [-inf, -inf, -inf]
5]
  1. Answer Calculation: We check f[i][j] values where i + j = m to update ans, the maximum score so far. Since m = 2, we will check f[2][0], f[1][1], and f[0][2] to find our answer.

Continuing the update process with i and j values:

  • When i = 1 and j = 1, k = 1:
    • Take from the start: f[1][1] can become max(-inf, f[0][1] + 2 * nums[0]) which is 9 + 2 * 1 = 11.
    • Take from the end: f[1][1] can become max(-inf, f[1][0] + 2 * nums[2]) which is 3 + 2 * 3 = 9. Since 11 is greater, f[1][1] becomes 11.

After updating all values, our table f looks like this:

1f = [
2  [0, 9, -inf],
3  [3, 11, -inf],
4  [-inf, -inf, -inf]
5]

Our maximum score ans is the maximum value in f where i + j = m, which in this case is f[1][1] = 11.

Thus, the final answer is 11; it's the maximum score we can get by performing 2 operations using the given nums and multipliers.

Python Solution

1from typing import List
2
3class Solution:
4    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
5        # The length of the nums and multipliers arrays
6        num_length, multipliers_length = len(nums), len(multipliers)
7      
8        # Initialize the dp (Dynamic Programming) array with negative infinity
9        # To accommodate for potential negative scores
10        dp = [[float('-inf')] * (multipliers_length + 1) for _ in range(multipliers_length + 1)]
11      
12        # The starting score is 0 when no multipliers have been applied
13        dp[0][0] = 0
14      
15        # Initialize the answer with negative infinity
16        max_score = float('-inf')
17      
18        # Loop through all the possible combinations of left and right operations
19        for left_count in range(multipliers_length + 1):
20            for right_count in range(multipliers_length - left_count + 1):
21                # The index of the current multiplier
22                current_multiplier_index = left_count + right_count - 1
23              
24                # Calculate the score if we take the number from the left
25                if left_count > 0:
26                    dp[left_count][right_count] = max(dp[left_count][right_count],
27                                                      dp[left_count - 1][right_count] + multipliers[current_multiplier_index] * nums[left_count - 1])
28              
29                # Calculate the score if we take the number from the right
30                if right_count > 0:
31                    dp[left_count][right_count] = max(dp[left_count][right_count],
32                                                      dp[left_count][right_count - 1] + multipliers[current_multiplier_index] * nums[num_length - right_count])
33              
34                # If we have used all multipliers, update the maximum score
35                if left_count + right_count == multipliers_length:
36                    max_score = max(max_score, dp[left_count][right_count])
37      
38        # Return the maximum score after using all multipliers
39        return max_score
40

Java Solution

1import java.util.Arrays;
2
3class Solution {
4
5    // This method calculates the maximum score from performing operations on the array `nums` using the `multipliers`.
6    public int maximumScore(int[] nums, int[] multipliers) {
7        int n = nums.length; // The length of the nums array
8        int m = multipliers.length; // The length of the multipliers array
9        int[][] dp = new int[m + 1][m + 1]; // DP array to store the intermediate solutions
10
11        // Initialize all values in the DP array to a very small number to ensure there's no overcount
12        for (int i = 0; i <= m; i++) {
13            Arrays.fill(dp[i], Integer.MIN_VALUE);
14        }
15        dp[0][0] = 0; // Base case: no operation gives score of 0
16
17        int maxScore = Integer.MIN_VALUE; // Variable to keep track of the maximum score
18
19        // Outer loop goes through all possible counts of operations
20        for (int i = 0; i <= m; ++i) {
21            // Inner loop considers different splits between left and right operations
22            for (int left = 0; left <= m - i; ++left) {
23                int right = i + left - 1;
24                // If we can take a left operation, update the DP value considering the left pick
25                if (left > 0) {
26                    dp[left][i - left] = Math.max(dp[left][i - left], dp[left - 1][i - left] + multipliers[right] * nums[left - 1]);
27                }
28                // If we can take a right operation, update the DP value considering the right pick
29                if (i - left > 0) {
30                    dp[left][i - left] = Math.max(dp[left][i - left], dp[left][i - left - 1] + multipliers[right] * nums[n - (i - left)]);
31                }
32                // If we have used all multipliers, update the maximum score if the current one is higher
33                if (i == m) {
34                    maxScore = Math.max(maxScore, dp[left][i - left]);
35                }
36            }
37        }
38        return maxScore; // Return the maximum score found
39    }
40}
41

C++ Solution

1class Solution {
2public:
3    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
4        // No need for such a large negative initial value, as scores can be negative.
5        // Let's use the minimum possible value for integers.
6        const int minInt = numeric_limits<int>::min();
7      
8        // Size of the nums and multipliers arrays.
9        int numSize = nums.size(), multiplierSize = multipliers.size();
10      
11        // Initializing a DP table where f[i][j] represents the maximum score possible
12        // using the first i elements from the beginning and the first j elements
13        // from the end of nums, after applying i + j multipliers.
14        vector<vector<int>> dp(multiplierSize + 1, vector<int>(multiplierSize + 1, minInt));
15      
16        // Base case: no elements picked and no multipliers applied.
17        dp[0][0] = 0;
18      
19        // Variable to store the final maximum score.
20        int maxScore = minInt;
21      
22        // Loop through all valid combinations of picks.
23        for (int i = 0; i <= multiplierSize; ++i) {
24            for (int j = 0; j <= multiplierSize - i; ++j) {
25                // The kth multiplier to apply.
26                int k = i + j - 1;
27              
28                // Update the dp value for picking from the beginning of nums.
29                if (i > 0) {
30                    dp[i][j] = max(dp[i][j], dp[i - 1][j] + multipliers[k] * nums[i - 1]);
31                }
32              
33                // Update the dp value for picking from the end of nums.
34                if (j > 0) {
35                    dp[i][j] = max(dp[i][j], dp[i][j - 1] + multipliers[k] * nums[numSize - j]);
36                }
37              
38                // If we've used all multipliers, compare with maxScore.
39                if (i + j == multiplierSize) {
40                    maxScore = max(maxScore, dp[i][j]);
41                }
42            }
43        }
44      
45        // Return the maximum score found.
46        return maxScore;
47    }
48};
49

Typescript Solution

1function maximumScore(nums: number[], multipliers: number[]): number {
2    // Initialize a large negative number that will never be reached in the problem.
3    const negativeInfinity = Number.MIN_SAFE_INTEGER;
4
5    // Retrieve the lengths of the input arrays.
6    const numLength = nums.length;
7    const multipliersLength = multipliers.length;
8
9    // Initialize a DP table with dimensions of multipliersLength + 1 and fill with negative infinity.
10    const dp = new Array(multipliersLength + 1)
11        .fill(0)
12        .map(() => new Array(multipliersLength + 1).fill(negativeInfinity));
13  
14    // Base case: if no numbers are picked, score is 0.
15    dp[0][0] = 0;
16
17    // This will hold the answer to the problem.
18    let maxScore = negativeInfinity;
19
20    // Iterate through all possible counts of elements picked from the beginning and end.
21    for (let i = 0; i <= multipliersLength; ++i) {
22        for (let j = 0; j <= multipliersLength - i; ++j) {
23            // Calculate the index for the current multiplier based on i and j.
24            const multiplierIndex = i + j - 1;
25          
26            // If an element from the front is picked, update the DP table accordingly.
27            if (i > 0) {
28                dp[i][j] = Math.max(
29                    dp[i][j],
30                    dp[i - 1][j] + nums[i - 1] * multipliers[multiplierIndex]
31                );
32            }
33
34            // If an element from the back is picked, update the DP table accordingly.
35            if (j > 0) {
36                dp[i][j] = Math.max(
37                    dp[i][j],
38                    dp[i][j - 1] + nums[numLength - j] * multipliers[multiplierIndex]
39                );
40            }
41
42            // If all multipliers have been used, consider the result as a possible max score.
43            if (i + j === multipliersLength) {
44                maxScore = Math.max(maxScore, dp[i][j]);
45            }
46        }
47    }
48
49    // Return the calculated maxScore after considering all possibilities.
50    return maxScore;
51}
52

Time and Space Complexity

The provided Python code aims to find the maximum score from multiplying elements of nums with multipliers based on specific rules. The function maximumScore utilizes dynamic programming with a 2D array f to store intermediate results.

Time Complexity:

The time complexity depends on two loops that iterate over the range (m + 1). The outer loop variable i runs from 0 to m, and for each value of i, the inner loop variable j runs up to (m - i). This essentially results in a total of roughly m/2 * m/2 iterations, which can be approximated to O(m^2) where m is the length of the multipliers list.

Moreover, the updates within the if conditions inside the nested loops also operate in constant time. Therefore, no additional complexity is added there.

Hence, the overall time complexity of this code is O(m^2).

Space Complexity:

The space complexity is determined by the size of the 2D array f, which has dimensions (m + 1) by (m + 1). So the total space used is (m + 1) * (m + 1), resulting in a space complexity of O(m^2) as well.

Thus, the overall space complexity of the algorithm is O(m^2).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫