LeetCode 3290 - Maximum Multiplication Score
This problem gives us two integer arrays: - a, which always has exactly 4 elements. - b, which has length at least 4 and can be as large as 100,000. We must select exactly four indices from b: The score obtained from such a selection is: Our goal is to maximize this score.
Difficulty: š” Medium
Topics: Array, Dynamic Programming
Solution
LeetCode 3290 - Maximum Multiplication Score
Problem Understanding
This problem gives us two integer arrays:
a, which always has exactly 4 elements.b, which has length at least 4 and can be as large as100,000.
We must select exactly four indices from b:
$$i_0 < i_1 < i_2 < i_3$$
The score obtained from such a selection is:
$$a[0] \times b[i_0] + a[1] \times b[i_1] + a[2] \times b[i_2] + a[3] \times b[i_3]$$
Our goal is to maximize this score.
In other words, we are trying to match each of the four coefficients in a with four elements from b, while preserving the order of selection in b. The selected values do not need to be adjacent, but their indices must be strictly increasing.
The constraints are very important:
a.length == 4b.lengthcan be up to100,000- Values can be negative or positive
Because b can contain one hundred thousand elements, any algorithm that tries all possible quadruples of indices is completely infeasible.
Several edge cases immediately stand out:
- All numbers may be negative.
- Some coefficients in
amay be negative while others are positive. - The optimal solution may intentionally choose very negative values from
bwhen multiplied by negative coefficients. - The answer itself can be much larger than 32-bit integer range because values can reach
10^5, and products can reach10^{10}.
The key challenge is efficiently finding the best ordered sequence of four choices.
Approaches
Brute Force
The most straightforward approach is to try every possible quadruple:
$$(i_0,i_1,i_2,i_3)$$
such that:
$$i_0 < i_1 < i_2 < i_3$$
For each quadruple, compute the score and keep the maximum.
This approach is correct because it explicitly evaluates every valid selection. The maximum score among all evaluated combinations must therefore be the answer.
Unfortunately, the number of possible quadruples is:
$$O(n^4)$$
where n = len(b).
With n = 100000, this is completely impossible.
Dynamic Programming
Notice that we only need to choose 4 elements. The number of coefficients is fixed and very small.
This suggests dynamic programming.
Suppose we process elements of b from left to right. At any point, we only care about the best score achievable after selecting:
- 0 elements
- 1 element
- 2 elements
- 3 elements
- 4 elements
Let:
$$dp[j]$$
represent the maximum score after choosing exactly j elements.
When we see a new value x = b[i], we may either:
- Skip it.
- Use it as the next selected element.
If we use it as the (j+1)-th selected element, then:
$$dp[j+1] = \max(dp[j+1], dp[j] + a[j]\times x)$$
Because we process b from left to right, index ordering is automatically preserved.
Since there are only 4 coefficients, each element of b performs only four DP transitions.
This gives an efficient linear solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(nā“) | O(1) | Tries every valid quadruple |
| Optimal DP | O(n) | O(1) | Maintains best scores for selecting 0 to 4 elements |
Algorithm Walkthrough
- Create a DP array of size 5.
dp[j] will store the maximum score obtainable after selecting exactly j elements from the processed prefix of b.
2. Initialize all states to negative infinity.
This marks them as impossible. 3. Set:
dp[0] = 0
Selecting zero elements yields score zero.
4. Process each value x in b from left to right.
5. For every x, update states in reverse order:
j = 3, 2, 1, 0
Reverse iteration is necessary so that the current element is not used multiple times during the same iteration.
6. For each j, attempt to make x the next selected element:
dp[j+1] =
max(
dp[j+1],
dp[j] + a[j] * x
)
- Continue until all elements of
bhave been processed. - The answer is stored in:
dp[4]
because we must select exactly four elements.
Why it works
The DP invariant is that after processing some prefix of b, dp[j] contains the maximum score achievable by selecting exactly j elements from that prefix while respecting index order.
When a new element b[i] is processed, every valid solution either ignores it or uses it as the next selected element. The transition considers both possibilities. Since every valid ordered selection can be built through these transitions, and every transition preserves the ordering constraint, dp[4] eventually becomes the maximum possible score over all valid quadruples.
Python Solution
from typing import List
class Solution:
def maxScore(self, a: List[int], b: List[int]) -> int:
NEG_INF = float("-inf")
dp = [NEG_INF] * 5
dp[0] = 0
for x in b:
for j in range(3, -1, -1):
if dp[j] != NEG_INF:
dp[j + 1] = max(
dp[j + 1],
dp[j] + a[j] * x
)
return int(dp[4])
The implementation directly follows the dynamic programming formulation.
The array dp contains five states corresponding to selecting 0, 1, 2, 3, or 4 elements.
Initially only dp[0] is valid because no elements have been chosen. Every other state is set to negative infinity to indicate impossibility.
For each value in b, we iterate backwards through the states. Reverse iteration ensures that a single element from b contributes to at most one selection level during that iteration.
The transition:
dp[j] + a[j] * x
represents selecting the current element as the next choice. Taking the maximum preserves the best score found so far.
After processing all elements, dp[4] contains the best score achievable using exactly four selected indices.
Go Solution
func maxScore(a []int, b []int) int64 {
const NEG_INF int64 = -(1 << 60)
dp := make([]int64, 5)
for i := 1; i < 5; i++ {
dp[i] = NEG_INF
}
for _, x := range b {
for j := 3; j >= 0; j-- {
if dp[j] == NEG_INF {
continue
}
candidate := dp[j] + int64(a[j])*int64(x)
if candidate > dp[j+1] {
dp[j+1] = candidate
}
}
}
return dp[4]
}
The Go solution is identical in logic to the Python version.
One important difference is that the function returns int64. Since values can reach 10^5, a product can reach 10^{10}, which exceeds 32-bit integer range. Using int64 guarantees correctness.
The DP array is also stored as int64, and every multiplication explicitly converts operands to int64 before performing arithmetic.
Worked Examples
Example 1
Input
a = [3, 2, 5, 6]
b = [2, -6, 4, -5, -3, 2, -7]
Initial state:
| State | Value |
|---|---|
| dp[0] | 0 |
| dp[1] | -ā |
| dp[2] | -ā |
| dp[3] | -ā |
| dp[4] | -ā |
After processing 2:
| State | Value |
|---|---|
| dp[0] | 0 |
| dp[1] | 6 |
| dp[2] | -ā |
| dp[3] | -ā |
| dp[4] | -ā |
After processing -6:
| State | Value |
|---|---|
| dp[0] | 0 |
| dp[1] | 6 |
| dp[2] | -6 |
| dp[3] | -ā |
| dp[4] | -ā |
After processing 4:
| State | Value |
|---|---|
| dp[0] | 0 |
| dp[1] | 12 |
| dp[2] | 14 |
| dp[3] | 14 |
| dp[4] | -ā |
After processing all remaining values, the final state becomes:
| State | Value |
|---|---|
| dp[4] | 26 |
Answer:
26
One optimal selection is indices:
0, 1, 2, 5
giving:
3Ć2 + 2Ć(-6) + 5Ć4 + 6Ć2 = 26
Example 2
Input
a = [-1, 4, 5, -2]
b = [-5, -1, -3, -2, -4]
Initial state:
| State | Value |
|---|---|
| dp[0] | 0 |
| dp[1] | -ā |
| dp[2] | -ā |
| dp[3] | -ā |
| dp[4] | -ā |
After processing -5:
| State | Value |
|---|---|
| dp[1] | 5 |
After processing -1:
| State | Value |
|---|---|
| dp[1] | 5 |
| dp[2] | 1 |
After processing -3:
| State | Value |
|---|---|
| dp[1] | 5 |
| dp[2] | 1 |
| dp[3] | -14 |
After processing -2:
| State | Value |
|---|---|
| dp[1] | 5 |
| dp[2] | 1 |
| dp[3] | -9 |
| dp[4] | -10 |
After processing -4:
| State | Value |
|---|---|
| dp[4] | -1 |
Answer:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element of b performs exactly 4 DP transitions |
| Space | O(1) | DP array always contains only 5 states |
The key observation is that the size of a is fixed at four. Therefore the inner loop always performs exactly four updates regardless of input size. This makes the running time linear in the length of b, while memory usage remains constant.
Test Cases
from typing import List
s = Solution()
assert s.maxScore([3, 2, 5, 6], [2, -6, 4, -5, -3, 2, -7]) == 26 # example 1
assert s.maxScore(
[-1, 4, 5, -2],
[-5, -1, -3, -2, -4]
) == -1 # example 2
assert s.maxScore(
[1, 1, 1, 1],
[1, 2, 3, 4]
) == 10 # exactly four elements
assert s.maxScore(
[1, 1, 1, 1],
[1, 2, 3, 4, 5]
) == 14 # choose largest valid subsequence
assert s.maxScore(
[-1, -1, -1, -1],
[-1, -1, -1, -1]
) == 4 # all negatives
assert s.maxScore(
[100000, 100000, 100000, 100000],
[100000, 100000, 100000, 100000]
) == 40000000000 # large values
assert s.maxScore(
[1, -1, 1, -1],
[5, -10, 5, -10]
) == 30 # alternating signs
assert s.maxScore(
[0, 0, 0, 0],
[7, -3, 9, 100]
) == 0 # all coefficients zero
assert s.maxScore(
[2, 3, 4, 5],
[-100, -100, -100, -100]
) == -1400 # forced negative result
assert s.maxScore(
[1, 2, 3, 4],
[1, 2, 3, 4, 5, 6, 7]
) == 60 # optimal subsequence near the end
Test Summary
| Test | Why |
|---|---|
| Example 1 | Verifies provided sample |
| Example 2 | Verifies provided sample with negative answer |
| Length exactly 4 | Smallest valid input size |
| Extra element available | Ensures optimal skipping works |
| All negatives | Tests sign handling |
| Large values | Verifies 64-bit arithmetic requirements |
| Alternating signs | Tests positive and negative interactions |
| All coefficients zero | Score should remain zero |
| Forced negative result | Ensures maximum among negative outcomes |
| Best choice near end | Verifies subsequence selection across long array |
Edge Cases
Minimum Length Array
When b has exactly four elements, there is only one possible valid selection. A buggy solution might still attempt unnecessary optimization logic or accidentally skip required elements. The DP formulation handles this naturally because the only possible sequence of transitions leads to the unique valid answer.
Negative Coefficients and Negative Values
A common mistake is assuming larger values are always better. If a coefficient in a is negative, selecting a very negative value from b may actually increase the score. The dynamic programming solution never relies on greedy choices and evaluates all valid possibilities through state transitions, ensuring correct handling of mixed signs.
Very Large Products
Each array value can be as large as 100000 in magnitude. A single multiplication can therefore produce values around 10^{10}. Using 32-bit integers would overflow. The Go solution explicitly uses int64, while Python integers automatically expand to arbitrary precision, guaranteeing correctness.
Multiple Optimal Prefix States
Different selections may lead to the same number of chosen elements but different scores. Keeping only the best score for each state is sufficient because future transitions depend solely on the current score and the number of selected elements. The DP invariant guarantees that any dominated state can never lead to a better final answer.