Scale Engineer

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

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

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

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.

Solutions

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 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 →

Next problem