Maximum Multiplication Score

Medium
1496.

Maximum Multiplication Score

Maximum Multiplication Score is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

You are given an array a of length 4 and an array b of length at least 4.

Choose four indices i0 < i1 < i2 < i3 of b. Their score is a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]. Return the maximum score achievable.

CodeKairo bound: values lie in [-10^4, 10^4] (LeetCode allows ±10^5) so that the answer fits in a 32-bit integer.

Example 1

Input
a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
Output
26
Explanation
Indices 0, 1, 2, 5: 3·2 + 2·(-6) + 5·4 + 6·2.

Example 2

Input
a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
Output
-1
Explanation
Indices 0, 1, 3, 4.

Example 3

Input
a = [1,1,1,1], b = [1,2,3,4,5]
Output
14

Constraints

  • a.length == 4
  • 4 <= b.length <= 10^5
  • -10^4 <= a[i], b[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} a
 * @param {number[]} b
 * @return {number}
 */
var maxScore = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Multiplication Score — Problem & Solution

Maximum Multiplication Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Multiplication Score is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array a of length 4 and an array b of length at least 4.

Choose four indices i0 < i1 < i2 < i3 of b. Their score is a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]. Return the maximum score achievable.

CodeKairo bound: values lie in [-10^4, 10^4] (LeetCode allows ±10^5) so that the answer fits in a 32-bit integer.

Example 1

Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
Output: 26
Explanation: Indices 0, 1, 2, 5: 3·2 + 2·(-6) + 5·4 + 6·2.

Example 2

Input: a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
Output: -1
Explanation: Indices 0, 1, 3, 4.

Example 3

Input: a = [1,1,1,1], b = [1,2,3,4,5]
Output: 14

Constraints

  • a.length == 4
  • 4 <= b.length <= 10^5
  • -10^4 <= a[i], b[i] <= 10^4

Hints for Maximum Multiplication Score

  1. Hint 1

    Choose the four indices left to right: the only thing that matters about a partial choice is how many of a it has used.

  2. Hint 2

    Let dp[k] be the best score after assigning a[0..k] to indices chosen among the elements scanned so far.

  3. Hint 3

    For each b[j], update k = 3, 2, 1, 0 (downwards): dp[k] = max(dp[k], dp[k-1] + a[k] * b[j]), with dp[-1] = 0.

How to solve Maximum Multiplication Score

A tiny knapsack over the four slots of a. Scanning b left to right, each element may fill the next slot after any partial assignment made strictly earlier, which keeps the indices increasing.

Approach

  1. Initialise dp[0..3] = -∞.
  2. For each x in b, for k from 3 down to 0: prev = (k == 0 ? 0 : dp[k-1]); if prev is finite, dp[k] = max(dp[k], prev + a[k] · x).
  3. Return dp[3].

Why it works

After scanning a prefix of b, dp[k] is the best way to place a[0..k] on increasing indices inside that prefix. A new element either is not used, or becomes the index of a[k] after an optimal placement of a[0..k-1] on earlier elements. Updating k downwards guarantees dp[k-1] still refers to strictly earlier elements.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Updating k upwards lets one element fill two slots.
  • Scores can be negative — start from -∞, not 0.
  • A greedy pick of the largest products ignores the index order.

Reference solution

Python

from typing import List

def maxScore(a: List[int], b: List[int]) -> int:
    NEG = -10**18
    dp = [NEG] * 4
    for x in b:
        for k in range(3, -1, -1):
            prev = 0 if k == 0 else dp[k - 1]
            if prev != NEG and prev + a[k] * x > dp[k]:
                dp[k] = prev + a[k] * x
    return dp[3]

Java

public static int maxScore(int[] a, int[] b) {
    final long NEG = Long.MIN_VALUE;
    long[] dp = {NEG, NEG, NEG, NEG};
    for (int x : b) {
        for (int k = 3; k >= 0; k--) {
            long prev = k == 0 ? 0 : dp[k - 1];
            if (prev == NEG) continue;
            long cand = prev + (long) a[k] * x;
            if (cand > dp[k]) dp[k] = cand;
        }
    }
    return (int) dp[3];
}

C++

int maxScore(vector<int>& a, vector<int>& b) {
    const long long NEG = LLONG_MIN;
    long long dp[4] = {NEG, NEG, NEG, NEG};
    for (int x : b) {
        for (int k = 3; k >= 0; k--) {
            long long prev = k == 0 ? 0 : dp[k - 1];
            if (prev == NEG) continue;
            long long cand = prev + (long long) a[k] * x;
            if (cand > dp[k]) dp[k] = cand;
        }
    }
    return (int) dp[3];
}

JavaScript

var maxScore = function(a, b) {
    var dp = [-Infinity, -Infinity, -Infinity, -Infinity];
    for (var j = 0; j < b.length; j++) {
        for (var k = 3; k >= 0; k--) {
            var prev = k === 0 ? 0 : dp[k - 1];
            if (prev !== -Infinity && prev + a[k] * b[j] > dp[k]) dp[k] = prev + a[k] * b[j];
        }
    }
    return dp[3];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming