Skip to content

3290. Maximum Multiplication Score

SourceWeekly Contest 415 Q2DifficultyMediumRating1692

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

Solutions

Solution 1: Memoization

Thinking

\(a\) has four entries; we pick four increasing indices in \(b\) and maximize the dot product. \(|b|\le 10^5\) forbids \(O(n^4)\) index tuples. There are only four stages, so we DP on the position in \(b\).

\(\textit{dfs}(i,j)\): \(i\) of \(a\) used, at \(b[j]\). Skip \(b[j]\), or take \(a[i]\times b[j]\) and advance both. Memoized states are \(4\times n\).

We design a function \(\textit{dfs}(i, j)\), which represents the maximum score that can be obtained starting from the \(i\)-th element of array \(a\) and the \(j\)-th element of array \(b\). Then the answer is \(\textit{dfs}(0, 0)\).

The function \(\textit{dfs}(i, j)\) is calculated as follows:

  • If \(j \geq \text{len}(b)\), it means array \(b\) has been completely traversed. At this point, if array \(a\) has also been completely traversed, return \(0\); otherwise, return negative infinity.
  • If \(i \geq \text{len}(a)\), it means array \(a\) has been completely traversed. Return \(0\).
  • Otherwise, we can either skip the \(j\)-th element of array \(b\) and move to the next element, i.e., \(\textit{dfs}(i, j + 1)\); or we can choose the \(j\)-th element of array \(b\), in which case the score is \(a[i] \times b[j]\) plus \(\textit{dfs}(i + 1, j + 1)\). We take the maximum of these two values as the return value of \(\textit{dfs}(i, j)\).

We can use memoization to avoid redundant calculations.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the lengths of arrays \(a\) and \(b\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if j >= len(b):
                return 0 if i >= len(a) else -inf
            if i >= len(a):
                return 0
            return max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1))

        return dfs(0, 0)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b) {
        int m = a.size(), n = b.size();
        long long f[m][n];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
            if (j >= n) {
                return i >= m ? 0 : LLONG_MIN / 2;
            }
            if (i >= m) {
                return 0;
            }
            if (f[i][j] != -1) {
                return f[i][j];
            }
            return f[i][j] = max(dfs(i, j + 1), 1LL * a[i] * b[j] + dfs(i + 1, j + 1));
        };
        return dfs(0, 0);
    }
};

 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
func maxScore(a []int, b []int) int64 {
    m, n := len(a), len(b)
    f := make([][]int64, m)
    for i := range f {
        f[i] = make([]int64, n)
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    var dfs func(i, j int) int64
    dfs = func(i, j int) int64 {
        if j >= n {
            if i >= m {
                return 0
            }
            return math.MinInt64 / 2
        }
        if i >= m {
            return 0
        }
        if f[i][j] != -1 {
            return f[i][j]
        }
        f[i][j] = max(dfs(i, j+1), int64(a[i])*int64(b[j])+dfs(i+1, j+1))
        return f[i][j]
    }
    return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function maxScore(a: number[], b: number[]): number {
    const [m, n] = [a.length, b.length];
    const f: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
    const dfs = (i: number, j: number): number => {
        if (j >= n) {
            return i >= m ? 0 : -Infinity;
        }
        if (i >= m) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        return (f[i][j] = Math.max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1)));
    };
    return dfs(0, 0);
}

Comments