Maximum Score from Performing Multiplication Operations

HARD

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 i^th 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 <= 10⁵
-1000 <= nums[i], multipliers[i] <= 1000

Approaches

Checkout 4 different approaches to solve Maximum Score from Performing Multiplication Operations. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

This approach directly translates the problem's choices into a recursive function. At each step i (from 0 to m-1), we have two choices: pick the leftmost available element or the rightmost available element from the nums array. We explore both paths recursively and return the maximum score obtained.

Algorithm

Define a recursive function solve(i, left, nums, multipliers).
Base Case: If i == multipliers.length, it means all multipliers have been used, so return 0.
Calculate the index of the rightmost available element: right = n - 1 - (i - left).
Recursive Step: Explore both choices:
- Pick from the left: scoreLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1, nums, multipliers).
- Pick from the right: scoreRight = multipliers[i] * nums[right] + solve(i + 1, left, nums, multipliers).
Return the maximum of scoreLeft and scoreRight.
The initial call from the main function is solve(0, 0, nums, multipliers).

We define a recursive helper function, say solve(i, left), which calculates the maximum score we can get from the i-th operation onwards, given that we have already picked left elements from the start of the original nums array.

The number of operations performed so far is i.
The number of elements picked from the left is left.
Therefore, the number of elements picked from the right is i - left.
The next available element from the left is at index left.
The next available element from the right is at index n - 1 - (i - left).

The recursive formula is: solve(i, left) = max( (multipliers[i] * nums[left]) + solve(i + 1, left + 1), (multipliers[i] * nums[n - 1 - (i - left)]) + solve(i + 1, left) )

The base case for the recursion is when i == m, meaning all multipliers have been used. In this case, the score from this point onwards is 0.

class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        return solve(0, 0, nums, multipliers);
    }

    private int solve(int i, int left, int[] nums, int[] multipliers) {
        // Base case: all multipliers have been used.
        if (i == multipliers.length) {
            return 0;
        }

        int n = nums.length;
        // The number of elements taken from the right is i - left.
        // So the right pointer is at n - 1 - (i - left).
        int right = n - 1 - (i - left);

        // Option 1: Choose the left element
        int pickLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1, nums, multipliers);
        
        // Option 2: Choose the right element
        int pickRight = multipliers[i] * nums[right] + solve(i + 1, left, nums, multipliers);

        return Math.max(pickLeft, pickRight);
    }
}

Complexity Analysis

Time Complexity: O(2^m) - For each of the `m` multipliers, the function branches into two recursive calls. This creates a binary recursion tree of depth `m`, leading to an exponential number of operations.Space Complexity: O(m) - The space complexity is determined by the maximum depth of the recursion stack, which is `m`.

Pros and Cons

Pros:

Simple to understand and implement as it directly models the decision-making process.

Cons:

Extremely inefficient due to an exponential number of redundant calculations.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Maximum Score from Performing Multiplication Operations. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Maximum Score from Performing Multiplication Operations

Patterns:

Dynamic Programming

Data Structures:

Array