What is the best approach to solving the Maximum Multiplication Score problem?

The best approach is to use dynamic programming combined with greedy selection to efficiently calculate the maximum score by selecting indices from array b.

How can dynamic programming be applied to this problem?

Dynamic programming is applied by creating a table that tracks the maximum score for selecting indices progressively from array b, ensuring all transitions are optimal.

What is the time complexity of solving this problem?

The time complexity varies depending on the approach. A straightforward solution may have O(n^2) complexity, but with optimizations, it can be reduced to O(n).

How does the greedy approach help in this problem?

The greedy approach helps by ensuring that, once the dynamic programming transitions are defined, we can quickly select the best indices that contribute to the score.

What are some common mistakes when solving the Maximum Multiplication Score problem?

Common mistakes include overcomplicating the solution with unnecessary loops, failing to optimize transitions in the DP table, or not considering the order of indices in array b.

#3290

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最高乘法得分

给你一个大小为 4 的整数数组 a 和一个大小至少为 4 的整数数组 b 。你需要从数组 b 中选择四个下标 i 0 , i 1 , i 2 , 和 i 3 ，并满足 i 0 1 2 3 。你的得分将是 a[0] * b[i 0 ] + a[1] * b[i 1 ] + a[2] * b[i …

数组动态规划

题目描述

给你一个大小为 4 的整数数组 a 和一个大小至少为 4 的整数数组 b。

你需要从数组 b 中选择四个下标 i₀, i₁, i₂, 和 i₃，并满足 i₀ < i₁ < i₂ < i₃。你的得分将是 a[0] * b[i₀] + a[1] * b[i₁] + a[2] * b[i₂] + a[3] * b[i₃] 的值。

返回你能够获得的最大得分。

示例 1：

输入： a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]

输出： 26

解释：
选择下标 0, 1, 2 和 5。得分为 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26。

示例 2：

输入： a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]

输出： -1

解释：
选择下标 0, 1, 3 和 4。得分为 (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1。

提示：

a.length == 4
4 <= b.length <= 10⁵
-10⁵ <= a[i], b[i] <= 10⁵

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $\textit{dfs}(i, j)$ ，表示从数组 $a$ 的第 $i$ 个元素开始，从数组 $b$ 的第 $j$ 个元素开始，能够获得的最大得分。那么答案就是 $\textit{dfs}(0, 0)$ 。

函数 $\textit{dfs}(i, j)$ 的计算方式如下：

如果 $j \geq \text{len}(b)$ ，表示数组 $b$ 已经遍历完了，此时如果数组 $a$ 也遍历完了，返回 $0$ ，否则返回负无穷；
如果 $i \geq \text{len}(a)$ ，表示数组 $a$ 已经遍历完了，返回 $0$ ；
否则，我们可以不选择数组 $b$ 的第 $j$ 个元素，直接跳到下一个元素，即 $\textit{dfs}(i, j + 1)$ ；也可以选择数组 $b$ 的第 $j$ 个元素，此时得分为 $a[i] \times b[j]$ ，再加上 $\textit{dfs}(i + 1, j + 1)$ 。我们取这两者的最大值作为 $\textit{dfs}(i, j)$ 的返回值。

我们可以使用记忆化搜索的方式，避免重复计算。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为数组 $a$ 和 $b$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate recognizes the importance of dynamic programming for state transitions.
question_mark
Candidate correctly identifies the need for greedy selection in conjunction with dynamic programming.
question_mark
Candidate efficiently manages the large input sizes with optimizations to reduce complexity.

warning

常见陷阱

外企场景

error
Overcomplicating the approach with unnecessary loops.
error
Failing to efficiently transition states in the DP table.
error
Misunderstanding the problem by not considering array b’s ordered indices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations in the size of array b, which might require different optimization strategies.
arrow_right_alt
Test the solution with varying values in array a and how it influences score maximization.
arrow_right_alt
Alter the problem to handle multiple sets of arrays for more complex scoring scenarios.

help

常见问题

外企场景

继续练习

#3291 形成目标字符串需要的最少字符串数 I #3292 形成目标字符串需要的最少字符串数 II #3287 求出数组中最大序列值