# Maximum Multiplication Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-multiplication-score)
Canonical: https://scaleengineer.com/dsa/problems/maximum-multiplication-score
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `a` of size 4 and another integer array `b` of size **at least** 4.

You need to choose 4 indices `i0`, `i1`, `i2`, and `i3` from the array `b` such that `i0 < i1 < i2 < i3`. Your score will be equal to the value `a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]`.

Return the **maximum** score you can achieve.

**Example 1:**

**Input:** a = \[3,2,5,6\], b = \[2,-6,4,-5,-3,2,-7\]

**Output:** 26

**Explanation:**  
We can choose the indices 0, 1, 2, and 5\. The score will be `3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26`.

**Example 2:**

**Input:** a = \[-1,4,5,-2\], b = \[-5,-1,-3,-2,-4\]

**Output:** \-1

**Explanation:**  
We can choose the indices 0, 1, 3, and 4\. The score will be `(-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1`.

**Constraints:**

* `a.length == 4`
* `4 <= b.length <= 105`
* `-105 <= a[i], b[i] <= 105`

# Approaches
## Brute Force with Four Nested Loops
The brute-force approach is the most intuitive way to solve the problem. It involves generating every possible valid combination of four indices from the array `b` and calculating the score for each combination. By keeping track of the highest score seen so far, we can find the maximum possible score.
**Time:** O(N^4) - Where N is the length of array `b`. The four nested loops result in a quartic time complexity, making it infeasible for N up to 10^5. · **Space:** O(1) - Constant extra space is used, as we only need a few variables to store the loop indices and the maximum score.
**Pros:** Simple to understand and straightforward to implement.; Correct for small input sizes.
**Cons:** Extremely inefficient due to its O(N^4) time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints on the size of array `b`.
### Explanation
This method systematically checks every single valid quadruplet of indices `(i0, i1, i2, i3)` where the indices are in increasing order. Four nested loops are a natural way to implement this. The outer loop selects the first index `i0`, the next loop selects `i1` ensuring it's greater than `i0`, and so on. For each valid set of four indices, we compute the multiplication score and compare it with our current maximum, updating it if the new score is higher. While simple, this exhaustive search is computationally very expensive.

```java
class Solution {
    public long maximumMultiplicationScore(int[] a, int[] b) {
        long maxScore = Long.MIN_VALUE;
        int n = b.length;
        for (int i0 = 0; i0 < n; i0++) {
            for (int i1 = i0 + 1; i1 < n; i1++) {
                for (int i2 = i1 + 1; i2 < n; i2++) {
                    for (int i3 = i2 + 1; i3 < n; i3++) {
                        long currentScore = (long) a[0] * b[i0] + 
                                            (long) a[1] * b[i1] + 
                                            (long) a[2] * b[i2] + 
                                            (long) a[3] * b[i3];
                        if (currentScore > maxScore) {
                            maxScore = currentScore;
                        }
                    }
                }
            }
        }
        return maxScore;
    }
}
```
### Algorithm
*   Initialize a variable `maxScore` to a very small number (e.g., `Long.MIN_VALUE`).
*   Let `n` be the length of array `b`.
*   Use a set of four nested loops to iterate through all possible combinations of indices `i0`, `i1`, `i2`, `i3` such that `0 <= i0 < i1 < i2 < i3 < n`.
*   The first loop runs for `i0` from `0` to `n - 4`.
*   The second loop runs for `i1` from `i0 + 1` to `n - 3`.
*   The third loop runs for `i2` from `i1 + 1` to `n - 2`.
*   The fourth loop runs for `i3` from `i2 + 1` to `n - 1`.
*   Inside the innermost loop, calculate the score: `score = a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]`.
*   Update `maxScore = Math.max(maxScore, score)`.
*   After the loops complete, return `maxScore`.

## Dynamic Programming with O(N) Space
A more efficient solution uses dynamic programming. The problem has optimal substructure and overlapping subproblems. We can build the solution iteratively. We first find the maximum scores possible by choosing one element, then use those results to find the maximum scores for choosing two elements, and so on, up to four elements.
**Time:** O(k * N) - Where `k=4` and N is the length of `b`. Since `k` is a constant, the complexity is linear, O(N). · **Space:** O(N) - We use an array of size N to store the DP states for each of the 4 stages. With the optimization, we use two arrays of size N, which is still O(N).
**Pros:** Efficient linear time complexity, which passes the given constraints.; Conceptually builds upon a standard DP pattern.
**Cons:** Requires linear space, which could be a limitation if memory is highly constrained, though it's acceptable for this problem's constraints.
### Explanation
Let's define `dp[k][i]` as the maximum score using `a[0]...a[k-1]` and `k` elements from `b` chosen from the prefix `b[0...i]`. The recurrence relation captures the two choices at each step `i` for each number of elements `k`: either we include `b[i]` as the `k`-th element or we don't. 

`dp[k][i] = max(dp[k][i-1], dp[k-1][i-1] + (long)a[k-1] * b[i])`

This would typically require a 2D DP table of size `4 x N`. However, we can observe that to compute the values for `k` elements, we only need the results for `k-1` elements. This allows for a space optimization where we only need to store the DP results for the previous `k` and the current `k`, reducing space to O(N).

```java
class Solution {
    public long maximumMultiplicationScore(int[] a, int[] b) {
        int n = b.length;
        long[] dp = new long[n];

        // k = 1
        dp[0] = (long) a[0] * b[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], (long) a[0] * b[i]);
        }

        // k = 2 to 4
        for (int k = 1; k < 4; k++) {
            long[] prev_dp = dp;
            dp = new long[n];
            // We need at least k elements (0-indexed)
            // so the first possible score is at index k.
            // dp[k] = prev_dp[k-1] + a[k]*b[k]
            // Initialize dp[k-1] to a very small value to handle the max correctly.
            dp[k-1] = Long.MIN_VALUE; 
            for (int i = k; i < n; i++) {
                long pick_b_i = prev_dp[i - 1] + (long) a[k] * b[i];
                long not_pick_b_i = dp[i - 1];
                dp[i] = Math.max(pick_b_i, not_pick_b_i);
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
*   Define `dp[k][i]` as the maximum score using the first `k` elements of `a` and `k` elements chosen from the prefix `b[0...i]`.
*   The state transition is `dp[k][i] = max(dp[k][i-1], dp[k-1][i-1] + a[k-1] * b[i])`.
*   `dp[k][i-1]` corresponds to not picking `b[i]`.
*   `dp[k-1][i-1] + a[k-1] * b[i]` corresponds to picking `b[i]` as the k-th element.
*   Since `dp[k]` only depends on `dp[k-1]`, we can optimize space from O(k*N) to O(N) by using two arrays: `prev_dp` for stage `k-1` and `curr_dp` for stage `k`.
*   Initialize a `dp` array of size `n` for the `k=1` case.
*   Iterate `k` from 2 to 4, calculating the `dp` values for the current stage using the values from the previous stage.
*   The final answer is the last element of the `dp` array after computing for `k=4`.

## Space-Optimized Dynamic Programming
The most optimal solution builds upon the dynamic programming approach but reduces the space complexity to constant. By cleverly ordering the loops and state updates, we can eliminate the need for O(N) space, using only a small, constant-size array to store the DP states.
**Time:** O(k * N) - Where `k=4` and N is the length of `b`. The two nested loops give a linear time complexity of O(N). · **Space:** O(1) - The space required is for the `dp` array of size 5, which is constant and does not depend on the input size N.
**Pros:** Most efficient solution with linear time and constant space.; Optimal in terms of both time and space complexity.
**Cons:** The logic, especially the backward iteration for `k`, can be less intuitive to understand initially compared to the O(N) space version.
### Explanation
This approach refines the DP solution to use O(1) space. We maintain a single array `dp` of size 5, where `dp[k]` represents the maximum score for choosing `k` elements. We iterate through each number in `b`. For each number, we update our `dp` array. The key is to iterate `k` from 4 down to 1. This ensures that when we compute the new value for `dp[k]`, the value of `dp[k-1]` we use is the one from before processing the current number from `b`, which is exactly what we need. This is a common space-optimization technique for DP problems similar to the 0/1 knapsack problem.

```java
class Solution {
    public long maximumMultiplicationScore(int[] a, int[] b) {
        int n = b.length;
        // dp[k] = max score using k elements
        long[] dp = new long[5];
        // Initialize with a very small value
        for (int i = 1; i <= 4; i++) {
            dp[i] = Long.MIN_VALUE;
        }
        // dp[0] = 0 is the base case: score with 0 elements is 0.

        for (int val : b) {
            // Iterate k backwards to use dp[k-1] from the previous state (before this val)
            for (int k = 4; k >= 1; k--) {
                // We can only form a score of k items if a score of k-1 items was possible.
                if (dp[k - 1] != Long.MIN_VALUE) {
                    dp[k] = Math.max(dp[k], dp[k - 1] + (long) a[k - 1] * val);
                }
            }
        }

        return dp[4];
    }
}
```
### Algorithm
*   Create a `long` array `dp` of size 5.
*   Initialize `dp[0] = 0` and `dp[1]` through `dp[4]` to a very small number like `Long.MIN_VALUE`.
*   `dp[k]` will store the maximum score using `k` elements from `a` and `k` elements from `b` from the prefix processed so far.
*   Iterate through each element `val` in the array `b`.
*   For each `val`, iterate backwards from `k = 4` down to `1`.
*   Inside the inner loop, update `dp[k]` using the formula: `dp[k] = max(dp[k], dp[k-1] + (long)a[k-1] * val)`.
*   The backward iteration is crucial. It ensures that when `dp[k]` is updated, `dp[k-1]` holds the value from *before* processing the current `val`, thus satisfying the `i0 < i1 < ...` constraint.
*   After iterating through all elements of `b`, `dp[4]` will hold the maximum possible score.

# Solutions
### Java

```java
class Solution {
private
  Long[][] f;
private
  int[] a;
private
  int[] b;
public
  long maxScore(int[] a, int[] b) {
    f = new Long[a.length][b.length];
    this.a = a;
    this.b = b;
    return dfs(0, 0);
  }
private
  long dfs(int i, int j) {
    if (j >= b.length) {
      return i >= a.length ? 0 : Long.MIN_VALUE / 2;
    }
    if (i >= a.length) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    return f[i][j] =
               Math.max(dfs(i, j + 1), 1L * a[i] * b[j] + dfs(i + 1, j + 1));
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxScore(vector<int> &a, vector<int> &b) {
    int m = a.size(), n = b.size();
    long long f[m][n];
    memset(f, -1, sizeof(f));
    auto dfs = [&](auto &&dfs, int i, int j) -> long long {
      if (j >= n) {
        return i >= m ? 0 : LLONG_MIN / 2;
      }
      if (i >= m) {
        return 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      return f[i][j] = max(dfs(dfs, i, j + 1),
                           1LL * a[i] * b[j] + dfs(dfs, i + 1, j + 1));
    };
    return dfs(dfs, 0, 0);
  }
};

```

### Python

```python
class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int: @ cache def dfs(i: int, j: int) -> int: if j >= len(b): return 0 if i >= len(a) else - inf if i >= len(a): return 0 return max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1)) return dfs(0, 0)

```