class Solution {
public:
long long maxScore(vector<int>& a, vector<int>& b) {
}
};
3290. 最高乘法得分
给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。
你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。
返回你能够获得的 最大 得分。
示例 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 == 44 <= b.length <= 105-105 <= a[i], b[i] <= 105原站题解
golang 解法, 执行用时: 128 ms, 内存消耗: 12.4 MB, 提交时间: 2024-09-18 16:45:39
func maxScore1(a, b []int) int64 {
n := len(b)
memo := make([][4]int64, n)
for i := range memo {
for j := range memo[i] {
memo[i][j] = math.MinInt64 // 表示没有计算过
}
}
var dfs func(int, int) int64
dfs = func(i, j int) int64 {
if j < 0 { // 选完了
return 0
}
if i < 0 { // j >= 0，没选完
return math.MinInt64 / 2 // 防止溢出
}
p := &memo[i][j]
if *p == math.MinInt64 { // 需要计算，并记忆化
*p = max(dfs(i-1, j), dfs(i-1, j-1)+int64(a[j])*int64(b[i]))
}
return *p
}
return dfs(n-1, 3)
}
// 递推
func maxScore(a, b []int) int64 {
n := len(b)
f := make([][5]int64, n+1)
for j := 1; j < 5; j++ {
f[0][j] = math.MinInt64 / 2
}
for i, y := range b {
for j, x := range a {
f[i+1][j+1] = max(f[i][j+1], f[i][j]+int64(x)*int64(y))
}
}
return f[n][4]
}
python3 解法, 执行用时: 1276 ms, 内存消耗: 37.4 MB, 提交时间: 2024-09-18 16:45:07
class Solution:
def maxScore1(self, a: List[int], b: List[int]) -> int:
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
if j < 0: # 选完了
return 0
if i < 0: # j >= 0，没选完
return -inf
return max(dfs(i - 1, j), dfs(i - 1, j - 1) + a[j] * b[i])
return dfs(len(b) - 1, 3)
# 递推
def maxScore(self, a: List[int], b: List[int]) -> int:
n = len(b)
f = [[0] * 5 for _ in range(n + 1)]
f[0][1:] = [-inf] * 4
for i, y in enumerate(b):
for j, x in enumerate(a):
f[i + 1][j + 1] = max(f[i][j + 1], f[i][j] + x * y)
return f[n][4]