# Maximum Score from Performing Multiplication Operations
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-from-performing-multiplication-operations
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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`

# Approaches
## 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.
**Time:** 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:** O(m) - The space complexity is determined by the maximum depth of the recursion stack, which is `m`.
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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)`.

## Top-Down Dynamic Programming (Memoization)
The brute-force recursive approach suffers from re-calculating the same subproblems. We can optimize this by storing the results of each subproblem `(i, left)` in a cache or memoization table. When the function is called with the same arguments again, we can directly return the stored result instead of re-computing it.
**Time:** O(m^2) - There are `O(m^2)` possible states for `(i, left)`, where `0 <= i < m` and `0 <= left <= i`. Each state is computed only once. · **Space:** O(m^2) - We use a 2D array of size `m x m` for the memoization table. The recursion stack adds an additional `O(m)` space.
**Pros:** Drastically improves performance over brute-force by eliminating redundant computations.; Guaranteed to find the optimal solution within the time limits for the given constraints.; Often intuitive to implement by adding a cache to a recursive solution.
**Cons:** Requires O(m^2) space, which might be substantial if `m` were much larger.
### Explanation
We use a 2D array, `memo[m][m]`, to store the results of `solve(i, left)`. The state `(i, left)` represents using the `i`-th multiplier and having taken `left` elements from the start. The number of elements taken from the left, `left`, can be at most `i`. So the state space for `left` is `0...i`. The total number of unique states is `O(m^2)`.

Before computing the result for `solve(i, left)`, we first check if it's already in our `memo` table. If it is, we return the value. Otherwise, we compute it, store it in the table, and then return it. This technique is called memoization, a form of top-down dynamic programming.

```java
class Solution {
    private int n, m;
    private int[] nums, multipliers;
    private Integer[][] memo;

    public int maximumScore(int[] nums, int[] multipliers) {
        this.n = nums.length;
        this.m = multipliers.length;
        this.nums = nums;
        this.multipliers = multipliers;
        this.memo = new Integer[m][m];
        return solve(0, 0);
    }

    private int solve(int i, int left) {
        if (i == m) {
            return 0;
        }
        if (memo[i][left] != null) {
            return memo[i][left];
        }

        int right = n - 1 - (i - left);

        int pickLeft = multipliers[i] * nums[left] + solve(i + 1, left + 1);
        int pickRight = multipliers[i] * nums[right] + solve(i + 1, left);

        return memo[i][left] = Math.max(pickLeft, pickRight);
    }
}
```
### Algorithm
- Create a 2D array `memo` of size `m x m` to store results. Initialize it with a value indicating 'not computed' (e.g., using `Integer` wrapper class and `null`).
- Define a recursive function `solve(i, left)`.
- Base Case: If `i == m`, return 0.
- Memoization Check: If `memo[i][left]` is not null, return the stored value.
- Recursive Step: Calculate scores for picking left and right, same as the brute-force approach.
- Store Result: Before returning, store the computed maximum score in `memo[i][left]`.
- The main function initializes the `memo` table and calls `solve(0, 0)`.

## Bottom-Up Dynamic Programming (Tabulation)
This approach is an iterative version of the memoized recursion, known as tabulation or bottom-up dynamic programming. Instead of starting from the top state `(0, 0)` and going down, we start from the base cases and build our way up to the solution. We use a 2D DP table, `dp[i][left]`, to store the maximum score.
**Time:** O(m^2) - We iterate through the relevant parts of the DP table using two nested loops, each running up to `m` times. · **Space:** O(m^2) - A 2D array of size `(m + 1) x (m + 1)` is used to store the DP states.
**Pros:** Avoids recursion overhead, which can lead to a slight performance improvement over memoization.; Provides a systematic, iterative way to build the solution from the ground up.
**Cons:** Requires O(m^2) space, same as the memoization approach.; Can sometimes be less intuitive to formulate the iteration order compared to memoization.
### Explanation
Let `dp[i][left]` be the maximum score obtainable from the remaining `m-i` operations (from operation `i` to `m-1`), given that `left` elements have already been taken from the start of `nums`. The state transition remains the same as in the recursive approach. Since the calculation for `dp[i]` depends on values from `dp[i+1]`, we must fill the table in decreasing order of `i`, from `m-1` down to `0`.

The base cases are `dp[m][left] = 0` for all `left`, as no more operations are left and thus no more score can be gained. The final answer we are looking for is `dp[0][0]`, which represents the maximum score starting from operation `0` with `0` elements taken from the left.

```java
class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        int n = nums.length;
        int m = multipliers.length;
        int[][] dp = new int[m + 1][m + 1];

        for (int i = m - 1; i >= 0; i--) {
            for (int left = i; left >= 0; left--) {
                int right = n - 1 - (i - left);
                int pickLeft = multipliers[i] * nums[left] + dp[i + 1][left + 1];
                int pickRight = multipliers[i] * nums[right] + dp[i + 1][left];
                dp[i][left] = Math.max(pickLeft, pickRight);
            }
        }

        return dp[0][0];
    }
}
```
### Algorithm
- Create a 2D DP table `dp` of size `(m + 1) x (m + 1)`.
- The base cases `dp[m][left] = 0` for all `left` are implicitly handled by Java's default array initialization.
- Iterate `i` from `m - 1` down to `0`.
- Inside this loop, iterate `left` from `i` down to `0`.
- Calculate the right index: `right = n - 1 - (i - left)`.
- Apply the recurrence relation to fill the table: `dp[i][left] = max(multipliers[i] * nums[left] + dp[i + 1][left + 1], multipliers[i] * nums[right] + dp[i + 1][left])`.
- The final answer is the value at `dp[0][0]`.

## Space-Optimized Bottom-Up DP
This is the most efficient approach in terms of memory. By observing the state transition in the bottom-up DP, we notice that to compute the values for row `i` of our `dp` table, we only need the values from the immediately following row, `i+1`. This allows us to optimize the space complexity from `O(m^2)` to `O(m)` by using only a 1D array to store the necessary previous state.
**Time:** O(m^2) - The time complexity remains the same as the standard bottom-up DP, with two nested loops. · **Space:** O(m) - We use two arrays of size `m+1` to store the DP states for the current and previous rows.
**Pros:** Most efficient solution in terms of space complexity.; Maintains the optimal O(m^2) time complexity while significantly reducing memory usage.
**Cons:** The logic for space optimization can be slightly more complex to derive and implement correctly compared to the 2D DP table approach.
### Explanation
Instead of a full 2D table, we can maintain a 1D array, `dp`, of size `m+1`. This array will represent the `(i+1)`-th row of the 2D DP table as we compute the `i`-th row. We iterate `i` from `m-1` down to `0`. In each iteration, we compute the values for the current row `i` based on the values from the previous iteration (which represent row `i+1`). A second temporary array, `next_dp`, is used to store the newly computed values for row `i` to avoid overwriting the values of row `i+1` that are still needed. After computing all values for row `i`, we replace the old `dp` array with `next_dp`.

```java
class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        int n = nums.length;
        int m = multipliers.length;
        int[] dp = new int[m + 1];

        for (int i = m - 1; i >= 0; i--) {
            // A new array to store the results for the current row `i`.
            // This could also be called `currentRow` or `dp_i`.
            int[] next_dp = new int[m + 1];
            for (int left = i; left >= 0; left--) {
                int right = n - 1 - (i - left);
                
                // Use the `dp` array (which holds results for row i+1) to calculate results for row i.
                int pickLeft = multipliers[i] * nums[left] + dp[left + 1];
                int pickRight = multipliers[i] * nums[right] + dp[left];
                
                next_dp[left] = Math.max(pickLeft, pickRight);
            }
            // The results for row `i` now become the 'previous' results for the next iteration (i-1).
            dp = next_dp;
        }

        return dp[0];
    }
}
```
### Algorithm
- Create a 1D array `dp` of size `m + 1`. This will hold the results for a given row `i+1`.
- Iterate `i` from `m - 1` down to `0`.
- Inside the loop, create a new temporary array `next_dp` of size `m + 1` to store results for row `i`.
- Iterate `left` from `i` down to `0`.
- Calculate the score for picking the left element: `multipliers[i] * nums[left] + dp[left + 1]`.
- Calculate the score for picking the right element: `multipliers[i] * nums[n - 1 - (i - left)] + dp[left]`.
- Store the maximum of these two scores in `next_dp[left]`.
- After the inner loop, update `dp` to be `next_dp` for the next iteration.
- The final answer is `dp[0]`.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  int[] multipliers;
private
  int[] nums;
private
  int n;
private
  int m;
public
  int maximumScore(int[] nums, int[] multipliers) {
    n = nums.length;
    m = multipliers.length;
    f = new Integer[m][m];
    this.nums = nums;
    this.multipliers = multipliers;
    return dfs(0, 0);
  }
private
  int dfs(int i, int j) {
    if (i >= m || j >= m || (i + j) >= m) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int k = i + j;
    int a = dfs(i + 1, j) + nums[i] * multipliers[k];
    int b = dfs(i, j + 1) + nums[n - 1 - j] * multipliers[k];
    f[i][j] = Math.max(a, b);
    return f[i][j];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumScore(vector<int> &nums, vector<int> &multipliers) {
    int n = nums.size(), m = multipliers.size();
    int f[m][m];
    memset(f, 0x3f, sizeof f);
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i >= m || j >= m || (i + j) >= m)
        return 0;
      if (f[i][j] != 0x3f3f3f3f)
        return f[i][j];
      int k = i + j;
      int a = dfs(i + 1, j) + nums[i] * multipliers[k];
      int b = dfs(i, j + 1) + nums[n - j - 1] * multipliers[k];
      return f[i][j] = max(a, b);
    };
    return dfs(0, 0);
  }
};

```

### Python

```python
class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int: @ cache def f(i, j, k): if k >= m or i >= n or j < 0: return 0 a = f(i + 1, j, k + 1) + nums[i] * multipliers[k] b = f(i, j - 1, k + 1) + nums[j] * multipliers[k] return max(a, b) n = len(nums) m = len(multipliers) return f(0, n - 1, 0)

```