# Maximum Score from Performing Multiplication Operations

## Problem#

We are given two array of integers `nums` and `multipliers` of size `n` and `m` respectively, where `n` >= `m`.

Begin with a score of `0`, we want to perform exactly `m` operations. On the ith operation, we will:

• Choose an integer `x` from either the start or the end of the array `nums`.
• Add `multipliers[i] * x` to your score.
• Remove `x` from the array `nums`.

Our task is to find the maximum score after performing `m` operations.

For example,

```Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: The 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, , adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.
```
```Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: The 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.
```

## Solution#

### Brute Force#

Based on problem description, at every ith operation we have two choices of multiplication which are `multipliers[i] * nums[left]` and `multipliers[i] * nums[right]`. Each of the result will then be added to the multiplication of the rest of `multipliers` with either `nums[left+1]` or `nums[right-1]`, hence the subproblems.

The subproblem, also called a `state`, indicates that we can use recursion to solve the problem. Each state is represented by:

1. `left` to indicate the left index to multiply by
2. `right` to indicate the right index to multiply by
3. `op` to indicate the number of the rest of operation

We could generate all possible states as follows: The algorithm is as follows:

1. Create an overload method of `MaximumScore` that takes three arguments: left, right and op
2. If `op` equals the length of `multipliers` which means we are done with all the operations, then it will return 0
3. Otherwise,
• Multiply `multipliers[op]` with `nums[left]`. Then, solve the subproblem for the next operation `op+1` with array `nums` range from `left+1` to `right`. Add the result of the subproblem to the multiplication.
• Multiply `multipliers[op]` with `nums[right]`. Then, solve the subproblem for the next operation `op+1` with array `nums` range from `left` to `right-1`. Add the result of the subproblem to the multiplication.
4. Return the maximum of the two results
5. Create the initial call which means we have done `0` operation so far with array `nums` range from `0` to `nums.Length - 1`

``````public int MaximumScore(int[] nums, int[] multipliers)
{
return MaximumScore(0, nums.Length - 1, 0);

int MaximumScore(int left, int right, int op)
{
if (op == multipliers.Length)
return 0;

return Math.Max(multipliers[op] * nums[left] + MaximumScore(left + 1, right, op + 1),
multipliers[op] * nums[right] + MaximumScore(left, right - 1, op + 1));
}
}
``````

#### Complexity Analysis#

Suppose `M` is the length of `multipliers` which is the same with the number of operations.

• Time Complexity: At each step we generate two subtree and the height of the tree is `M`. The total number of generated nodes is 2M. Since, we traverse all the nodes, then the complexity will be O(2M).
• Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(M).

### Top-down Dynamic Programming#

Top-down Dynamic Programming approach can be viewed as the improvement of Brute Force approach. We can see from below image that there are some repeated states. These states should be memoized. To formalize dynamic programming solution, we need to combine three things:

1. A function or data structure that answers the problem for a given state
The function is `MaximumScore(left, right, op)` that denotes the maximum score we get after doing `op` operations on `nums` array ranges from `left` to `right`.
2. A recurrence relation that defines transition between states

MaximumScore(left, right, op) = Max(
multipliers[op] * nums[left] + MaximumScore(left + 1, right, op + 1), multipliers[op] * nums[right] + MaximumScore(left, right - 1, op + 1)
)

3. Base cases
`MaximumScore(*, *, op) = 0` when `op` equals length of `multipliers`.

By memoizing the visited state, we can reduce the complexity.

``````public int MaximumScore(int[] nums, int[] multipliers)
{
Dictionary<(int, int, int), int> memo = new Dictionary<(int, int, int), int>();
return MaximumScore(0, nums.Length - 1, 0);

int MaximumScore(int left, int right, int op)
{
if (op == multipliers.Length)
return 0;

if (!memo.TryGetValue((left, right, op), out var result))
{
result = Math.Max(multipliers[op] * nums[left] + MaximumScore(left + 1, right, op + 1),
multipliers[op] * nums[right] + MaximumScore(left, right - 1, op + 1));

}

return result;
}
}
``````

#### Complexity Analysis#

Suppose `M` is the length of `multipliers` which is the same with the number of operations.

• Time Complexity: By memoizing the state, it will reduce the number of recursion call to the subproblems from 2M to at most M2 because at each state we have two calls that must be performed. Therefore, the complexity will be O(M2).
• Space Complexity: The `memo` will store at most M2 number of state, thus the complexity will be O(M2).

### Bottom-up Dynamic Programming#

Converting top-down to bottom-up technique is not straightforward. However, the rule of thumb is to use table or tabulation.

We can construct a table `M+1 * M+1` where `M` is the length of `multipliers`. We use `M+1` because we need placeholder to avoid `IndexOutOfBoundsException`.

Based on recursion tree in top-down approach, we work bottom up and compress the tree from the bottom in such way that it will fill only half of the table we provide. ``````public int MaximumScore(int[] nums, int[] multipliers)
{
int m = multipliers.Length;
int n = nums.Length;
int[,] dp = new int[m + 1, m + 1];

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

return dp[0, 0];
}
``````

#### Complexity Analysis#

Suppose `M` is the length of `multipliers`.

• Time Complexity: Since the total of iteration is half of the matrix or M2/2, then the complexity is O(M2).
• Space Complexity: `dp` array has size (M+1)2, thus the complexity is O(M2).