Maximum Multiplication Score

Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8



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

1
2
3
4
5
6
7
8



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

Solution

Method 1 – Dynamic Programming (State Compression)

Intuition

We need to pick 4 increasing indices from b and assign them to a[0], a[1], a[2], a[3] in order to maximize the sum a[0]*b[i0] + a[1]*b[i1] + a[2]*b[i2] + a[3]*b[i3]. Since a has only 4 elements, we can use dynamic programming where the state is the number of elements picked so far and the current index in b.

Approach

Let dp[i][j] be the maximum score by picking i elements from b[0..j].
Initialize dp[0][j] = 0 for all j.
For i from 1 to 4:
- For j from i-1 to len(b)-1:
  - For k from i-2 to j-1:
    - dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i-1]*b[j])
The answer is the maximum dp[4][j] for j in [3, len(b)-1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int maximumScore(vector<int>& a, vector<int>& b) {
        int n = b.size();
        vector<vector<int>> dp(5, vector<int>(n, INT_MIN));
        for (int j = 0; j < n; ++j) dp[0][j] = 0;
        for (int i = 1; i <= 4; ++i) {
            for (int j = i-1; j < n; ++j) {
                for (int k = i-2; k < j; ++k) {
                    if (dp[i-1][k] != INT_MIN)
                        dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i-1]*b[j]);
                }
            }
        }
        int ans = INT_MIN;
        for (int j = 3; j < n; ++j) ans = max(ans, dp[4][j]);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func maximumScore(a []int, b []int) int {
    n := len(b)
    dp := make([][]int, 5)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = -1 << 31
        }
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 0
    }
    for i := 1; i <= 4; i++ {
        for j := i-1; j < n; j++ {
            for k := i-2; k < j; k++ {
                if dp[i-1][k] != -1<<31 {
                    v := dp[i-1][k] + a[i-1]*b[j]
                    if v > dp[i][j] {
                        dp[i][j] = v
                    }
                }
            }
        }
    }
    ans := -1 << 31
    for j := 3; j < n; j++ {
        if dp[4][j] > ans {
            ans = dp[4][j]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public int maximumScore(int[] a, int[] b) {
        int n = b.length;
        int[][] dp = new int[5][n];
        for (int i = 0; i < 5; ++i) Arrays.fill(dp[i], Integer.MIN_VALUE);
        for (int j = 0; j < n; ++j) dp[0][j] = 0;
        for (int i = 1; i <= 4; ++i) {
            for (int j = i-1; j < n; ++j) {
                for (int k = i-2; k < j; ++k) {
                    if (dp[i-1][k] != Integer.MIN_VALUE)
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + a[i-1]*b[j]);
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int j = 3; j < n; ++j) ans = Math.max(ans, dp[4][j]);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    fun maximumScore(a: IntArray, b: IntArray): Int {
        val n = b.size
        val dp = Array(5) { IntArray(n) { Int.MIN_VALUE } }
        for (j in 0 until n) dp[0][j] = 0
        for (i in 1..4) {
            for (j in i-1 until n) {
                for (k in i-2 until j) {
                    if (dp[i-1][k] != Int.MIN_VALUE)
                        dp[i][j] = maxOf(dp[i][j], dp[i-1][k] + a[i-1]*b[j])
                }
            }
        }
        var ans = Int.MIN_VALUE
        for (j in 3 until n) ans = maxOf(ans, dp[4][j])
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def maximumScore(self, a: list[int], b: list[int]) -> int:
        n = len(b)
        dp = [[float('-inf')] * n for _ in range(5)]
        for j in range(n):
            dp[0][j] = 0
        for i in range(1, 5):
            for j in range(i-1, n):
                for k in range(i-2, j):
                    if dp[i-1][k] != float('-inf'):
                        dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i-1]*b[j])
        ans = float('-inf')
        for j in range(3, n):
            ans = max(ans, dp[4][j])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
    pub fn maximum_score(a: Vec<i32>, b: Vec<i32>) -> i32 {
        let n = b.len();
        let mut dp = vec![vec![i32::MIN; n]; 5];
        for j in 0..n { dp[0][j] = 0; }
        for i in 1..=4 {
            for j in (i-1)..n {
                for k in (i-2)..j {
                    if dp[i-1][k] != i32::MIN {
                        dp[i][j] = dp[i][j].max(dp[i-1][k] + a[i-1]*b[j]);
                    }
                }
            }
        }
        let mut ans = i32::MIN;
        for j in 3..n { ans = ans.max(dp[4][j]); }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    maximumScore(a: number[], b: number[]): number {
        const n = b.length;
        const dp = Array.from({length: 5}, () => Array(n).fill(-Infinity));
        for (let j = 0; j < n; ++j) dp[0][j] = 0;
        for (let i = 1; i <= 4; ++i) {
            for (let j = i-1; j < n; ++j) {
                for (let k = i-2; k < j; ++k) {
                    if (dp[i-1][k] !== -Infinity)
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + a[i-1]*b[j]);
                }
            }
        }
        let ans = -Infinity;
        for (let j = 3; j < n; ++j) ans = Math.max(ans, dp[4][j]);
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^2), where n is the length of b, since for each of the 4 picks, we check all previous positions.
🧺 Space complexity: O(n), for the DP table.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dynamic Programming (State Compression)#

Intuition#

Approach#

Code#

Complexity#