来源第 415 场周赛 Q2难度中等分数1692
题目描述
给你一个大小为 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
解法
方法一：记忆化搜索
思考
\(a\) 只有 \(4\) 个数，要从 \(b\) 中按顺序选 \(4\) 个位置相乘求和，最大化。 \(|b|\le 10^5\)，枚举四下标为 \(O(n^4)\)。阶段只有 \(4\)，对 \(b\) 的位置做匹配 DP。
\(\textit{dfs}(i,j)\)：已用掉 \(a\) 的前 \(i\) 个、考虑到 \(b[j]\)。可跳过 \(b[j]\)，或选中并加上 \(a[i]\times b[j]\)。记忆化状态 \(4\times n\)。
我们设计一个函数 \(\textit{dfs}(i, j)\)，表示从数组 \(a\) 的第 \(i\) 个元素开始，从数组 \(b\) 的第 \(j\) 个元素开始，能够获得的最大得分。那么答案就是 \(\textit{dfs}(0, 0)\)。
函数 \(\textit{dfs}(i, j)\) 的计算方式如下：
- 如果 \(j \geq \textit{len}(b)\)，表示数组 \(b\) 已经遍历完了，此时如果数组 \(a\) 也遍历完了，返回 \(0\)，否则返回负无穷；
- 如果 \(i \geq \textit{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(mn)\)，空间复杂度 \(O(mn)\)。其中 \(m\) 和 \(n\) 分别为数组 \(a\) 和 \(b\) 的长度。
| 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);
}
|
方法二：动态规划
思考
\(a\) 只有 \(4\) 个数，要从 \(b\) 中按顺序选 \(4\) 个位置相乘求和，最大化。 \(|b|\le 10^5\)，枚举四下标为 \(O(n^4)\)。阶段只有 \(4\)，另一维是 \(b\) 的位置。
在阶段 \(i\)、位置 \(b[j]\)，下一步要么仍停在阶段 \(i\) 看 \(b[j+1]\)，要么加上 \(a[i]\times b[j]\) 后进入阶段 \(i+1\)。按这个递推搜索时仍会先调用 \(j+1\) 再返回，调用链深度为 \(n\)，栈会溢出。
从 \(b\) 的末尾往前走时，下一列已经就绪。令 \(f[i][j]\) 为该最大得分； \(a\) 已经用完时后缀得分为 \(0\)，否则走到 \(b\) 的尽头记为负无穷。
我们从 \(j=n-1\) 填到 \(0\)，返回 \(f[0][0]\)。
令 \(f[i][j]\) 表示从数组 \(a\) 的第 \(i\) 个元素、数组 \(b\) 的第 \(j\) 个元素开始能够获得的最大得分。答案为 \(f[0][0]\)。
若 \(j = n\)，数组 \(b\) 已经走完。数组 \(a\) 也走完时值为 \(0\)，否则为负无穷。若 \(i = m\)，数组 \(a\) 已经走完，剩下的 \(b\) 得分为 \(0\)。
否则可以跳过 \(b[j]\)，得分为 \(f[i][j + 1]\)；也可以选中它，得分为 \(a[i] \times b[j] + f[i + 1][j + 1]\)。 \(f[i][j]\) 取两者的较大值。
我们从 \(j = n - 1\) 往前计算到 \(0\)。
时间复杂度 \(O(mn)\)，空间复杂度 \(O(mn)\)。其中 \(m\) 和 \(n\) 分别为数组 \(a\) 和 \(b\) 的长度。
| class Solution:
def maxScore(self, a: List[int], b: List[int]) -> int:
m, n = len(a), len(b)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
f[i][n] = -inf
for j in range(n - 1, -1, -1):
for i in range(m - 1, -1, -1):
f[i][j] = max(f[i][j + 1], a[i] * b[j] + f[i + 1][j + 1])
return f[0][0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public long maxScore(int[] a, int[] b) {
int m = a.length, n = b.length;
long[][] f = new long[m + 1][n + 1];
for (int i = 0; i < m; ++i) {
f[i][n] = Long.MIN_VALUE / 2;
}
for (int j = n - 1; j >= 0; --j) {
for (int i = m - 1; i >= 0; --i) {
f[i][j] = Math.max(f[i][j + 1], 1L * a[i] * b[j] + f[i + 1][j + 1]);
}
}
return f[0][0];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
long long maxScore(vector<int>& a, vector<int>& b) {
int m = a.size(), n = b.size();
vector<vector<long long>> f(m + 1, vector<long long>(n + 1));
for (int i = 0; i < m; ++i) {
f[i][n] = LLONG_MIN / 2;
}
for (int j = n - 1; j >= 0; --j) {
for (int i = m - 1; i >= 0; --i) {
f[i][j] = max(f[i][j + 1], 1LL * a[i] * b[j] + f[i + 1][j + 1]);
}
}
return f[0][0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | func maxScore(a []int, b []int) int64 {
m, n := len(a), len(b)
f := make([][]int64, m+1)
for i := range f {
f[i] = make([]int64, n+1)
}
for i := 0; i < m; i++ {
f[i][n] = math.MinInt64 / 2
}
for j := n - 1; j >= 0; j-- {
for i := m - 1; i >= 0; i-- {
f[i][j] = max(f[i][j+1], int64(a[i])*int64(b[j])+f[i+1][j+1])
}
}
return f[0][0]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | function maxScore(a: number[], b: number[]): number {
const m = a.length;
const n = b.length;
const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 0; i < m; ++i) {
f[i][n] = -Infinity;
}
for (let j = n - 1; j >= 0; --j) {
for (let i = m - 1; i >= 0; --i) {
f[i][j] = Math.max(f[i][j + 1], a[i] * b[j] + f[i + 1][j + 1]);
}
}
return f[0][0];
}
|