Maximum Multiplication Score

Med

#2921Time: 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).

Patterns

Dynamic Programming

Data structures

Array

Prompt

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 i₀, i₁, i₂, and i₃ from the array b such that i₀ < i₁ < i₂ < i₃. Your score will be equal to the value a[0] * b[i₀] + a[1] * b[i₁] + a[2] * b[i₂] + a[3] * b[i₃].

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 <= 10⁵
-10⁵ <= a[i], b[i] <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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).

1class Solution {2    public long maximumMultiplicationScore(int[] a, int[] b) {3        int n = b.length;4        long[] dp = new long[n];5 6        // k = 17        dp[0] = (long) a[0] * b[0];8        for (int i = 1; i < n; i++) {9            dp[i] = Math.max(dp[i - 1], (long) a[0] * b[i]);10        }11 12        // k = 2 to 413        for (int k = 1; k < 4; k++) {14            long[] prev_dp = dp;15            dp = new long[n];16            // We need at least k elements (0-indexed)17            // so the first possible score is at index k.18            // dp[k] = prev_dp[k-1] + a[k]*b[k]19            // Initialize dp[k-1] to a very small value to handle the max correctly.20            dp[k-1] = Long.MIN_VALUE; 21            for (int i = k; i < n; i++) {22                long pick_b_i = prev_dp[i - 1] + (long) a[k] * b[i];23                long not_pick_b_i = dp[i - 1];24                dp[i] = Math.max(pick_b_i, not_pick_b_i);25            }26        }27 28        return dp[n - 1];29    }30}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public long maximumMultiplicationScore(int[] a, int[] b) {3        long maxScore = Long.MIN_VALUE;4        int n = b.length;5        for (int i0 = 0; i0 < n; i0++) {6            for (int i1 = i0 + 1; i1 < n; i1++) {7                for (int i2 = i1 + 1; i2 < n; i2++) {8                    for (int i3 = i2 + 1; i3 < n; i3++) {9                        long currentScore = (long) a[0] * b[i0] + 10                                            (long) a[1] * b[i1] + 11                                            (long) a[2] * b[i2] + 12                                            (long) a[3] * b[i3];13                        if (currentScore > maxScore) {14                            maxScore = currentScore;15                        }16                    }17                }18            }19        }20        return maxScore;21    }22}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public long maximumMultiplicationScore(int[] a, int[] b) {3        int n = b.length;4        // dp[k] = max score using k elements5        long[] dp = new long[5];6        // Initialize with a very small value7        for (int i = 1; i <= 4; i++) {8            dp[i] = Long.MIN_VALUE;9        }10        // dp[0] = 0 is the base case: score with 0 elements is 0.11 12        for (int val : b) {13            // Iterate k backwards to use dp[k-1] from the previous state (before this val)14            for (int k = 4; k >= 1; k--) {15                // We can only form a score of k items if a score of k-1 items was possible.16                if (dp[k - 1] != Long.MIN_VALUE) {17                    dp[k] = Math.max(dp[k], dp[k - 1] + (long) a[k - 1] * val);18                }19            }20        }21 22        return dp[4];23    }24}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  Long[][] f;4private5  int[] a;6private7  int[] b;8public9  long maxScore(int[] a, int[] b) {10    f = new Long[a.length][b.length];11    this.a = a;12    this.b = b;13    return dfs(0, 0);14  }15private16  long dfs(int i, int j) {17    if (j >= b.length) {18      return i >= a.length ? 0 : Long.MIN_VALUE / 2;19    }20    if (i >= a.length) {21      return 0;22    }23    if (f[i][j] != null) {24      return f[i][j];25    }26    return f[i][j] =27               Math.max(dfs(i, j + 1), 1L * a[i] * b[j] + dfs(i + 1, j + 1));28  }29}

1class Solution {2public:3  long long maxScore(vector<int> &a, vector<int> &b) {4    int m = a.size(), n = b.size();5    long long f[m][n];6    memset(f, -1, sizeof(f));7    auto dfs = [&](auto &&dfs, int i, int j) -> long long {8      if (j >= n) {9        return i >= m ? 0 : LLONG_MIN / 2;10      }11      if (i >= m) {12        return 0;13      }14      if (f[i][j] != -1) {15        return f[i][j];16      }17      return f[i][j] = max(dfs(dfs, i, j + 1),18                           1LL * a[i] * b[j] + dfs(dfs, i + 1, j + 1));19    };20    return dfs(dfs, 0, 0);21  }22};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  Long[][] f;4private5  int[] a;6private7  int[] b;8public9  long maxScore(int[] a, int[] b) {10    f = new Long[a.length][b.length];11    this.a = a;12    this.b = b;13    return dfs(0, 0);14  }15private16  long dfs(int i, int j) {17    if (j >= b.length) {18      return i >= a.length ? 0 : Long.MIN_VALUE / 2;19    }20    if (i >= a.length) {21      return 0;22    }23    if (f[i][j] != null) {24      return f[i][j];25    }26    return f[i][j] =27               Math.max(dfs(i, j + 1), 1L * a[i] * b[j] + dfs(i + 1, j + 1));28  }29}

1class Solution {2public:3  long long maxScore(vector<int> &a, vector<int> &b) {4    int m = a.size(), n = b.size();5    long long f[m][n];6    memset(f, -1, sizeof(f));7    auto dfs = [&](auto &&dfs, int i, int j) -> long long {8      if (j >= n) {9        return i >= m ? 0 : LLONG_MIN / 2;10      }11      if (i >= m) {12        return 0;13      }14      if (f[i][j] != -1) {15        return f[i][j];16      }17      return f[i][j] = max(dfs(dfs, i, j + 1),18                           1LL * a[i] * b[j] + dfs(dfs, i + 1, j + 1));19    };20    return dfs(dfs, 0, 0);21  }22};

1class Solution:2    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)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.