Maximum Multiplication Score

MEDIUM

Description

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

Checkout 3 different approaches to solve Maximum Multiplication Score. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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

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];
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

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

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));
  }
}

Video Solution

Watch the video walkthrough for Maximum Multiplication Score

Patterns:

Dynamic Programming

Data Structures:

Array