class Solution {
public:
long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
}
};
100386. 超级饮料的最大强化能量
来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。
你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。
返回在接下来的 n 小时内你能获得的 最大 总强化能量。
注意 你可以选择从饮用任意一种能量饮料开始。
示例 1：
输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
输出：5
解释：
要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。
示例 2：
输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
输出：7
解释：
提示：
n == energyDrinkA.length == energyDrinkB.length3 <= n <= 1051 <= energyDrinkA[i], energyDrinkB[i] <= 105原站题解
javascript 解法, 执行用时: 222 ms, 内存消耗: 90 MB, 提交时间: 2024-11-01 12:38:57
/**
* @param {number[]} energyDrinkA
* @param {number[]} energyDrinkB
* @return {number}
*/
var maxEnergyBoost = function(energyDrinkA, energyDrinkB) {
const n = energyDrinkA.length;
const d = Array.from({ length: n + 1 }, () => [0, 0]);
for (let i = 1; i <= n; i++) {
d[i][0] = d[i - 1][0] + energyDrinkA[i - 1];
d[i][1] = d[i - 1][1] + energyDrinkB[i - 1];
if (i >= 2) {
d[i][0] = Math.max(d[i][0], d[i - 2][1] + energyDrinkA[i - 1]);
d[i][1] = Math.max(d[i][1], d[i - 2][0] + energyDrinkB[i - 1]);
}
}
return Math.max(d[n][0], d[n][1]);
};
java 解法, 执行用时: 29 ms, 内存消耗: 57.5 MB, 提交时间: 2024-10-19 14:09:34
class Solution {
public long maxEnergyBoost(int[] a, int[] b) {
int n = a.length;
long[][] f = new long[n + 2][2];
for (int i = 0; i < n; i++) {
f[i + 2][0] = Math.max(f[i + 1][0], f[i][1]) + a[i];
f[i + 2][1] = Math.max(f[i + 1][1], f[i][0]) + b[i];
}
return Math.max(f[n + 1][0], f[n + 1][1]);
}
public long maxEnergyBoost2(int[] a, int[] b) {
int n = a.length;
int[][] c = {a, b};
long[][] memo = new long[n][2];
return Math.max(dfs(n - 1, 0, c, memo), dfs(n - 1, 1, c, memo));
}
private long dfs(int i, int j, int[][] c, long[][] memo) {
if (i < 0) {
return 0;
}
if (memo[i][j] > 0) { // 之前计算过
return memo[i][j];
}
return memo[i][j] = Math.max(dfs(i - 1, j, c, memo), dfs(i - 2, j ^ 1, c, memo)) + c[j][i];
}
}
golang 解法, 执行用时: 112 ms, 内存消耗: 32.5 MB, 提交时间: 2024-10-19 14:08:43
func maxEnergyBoost(a, b []int) int64 {
n := len(a)
c := [2][]int{a, b}
memo := make([][2]int64, n)
var dfs func(int, int) int64
dfs = func(i, j int) int64 {
if i < 0 {
return 0
}
p := &memo[i][j]
if *p == 0 { // 首次计算
*p = max(dfs(i-1, j), dfs(i-2, j^1)) + int64(c[j][i])
}
return *p
}
return max(dfs(n-1, 0), dfs(n-1, 1))
}
func maxEnergyBoost2(a, b []int) int64 {
n := len(a)
f := make([][2]int64, n+2)
for i, x := range a {
f[i+2][0] = max(f[i+1][0], f[i][1]) + int64(x)
f[i+2][1] = max(f[i+1][1], f[i][0]) + int64(b[i])
}
return max(f[n+1][0], f[n+1][1])
}
cpp 解法, 执行用时: 23 ms, 内存消耗: 206 MB, 提交时间: 2024-10-19 14:08:20
class Solution {
public:
long long maxEnergyBoost(vector<int>& a, vector<int>& b) {
int n = a.size();
vector<array<long long, 2>> f(n + 2);
for (int i = 0; i < n; i++) {
f[i + 2][0] = max(f[i + 1][0], f[i][1]) + a[i];
f[i + 2][1] = max(f[i + 1][1], f[i][0]) + b[i];
}
return max(f[n + 1][0], f[n + 1][1]);
}
long long maxEnergyBoost2(vector<int>& a, vector<int>& b) {
int n = a.size();
vector<int> c[2] = {move(a), move(b)};
vector<array<long long, 2>> memo(n);
auto dfs = [&](auto&& dfs, int i, int j) -> long long {
if (i < 0) {
return 0;
}
auto& p = memo[i][j]; // 注意这里是引用
if (p) { // 之前计算过
return p;
}
return p = max(dfs(dfs, i - 1, j), dfs(dfs, i - 2, j ^ 1)) + c[j][i];
};
return max(dfs(dfs, n - 1, 0), dfs(dfs, n - 1, 1));
}
};
python3 解法, 执行用时: 1118 ms, 内存消耗: 444.3 MB, 提交时间: 2024-10-19 14:07:48
class Solution:
def maxEnergyBoost(self, a: List[int], b: List[int]) -> int:
c = (a, b)
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
if i < 0:
return 0
return max(dfs(i - 1, j), dfs(i - 2, j ^ 1)) + c[j][i]
return max(dfs(len(a) - 1, 0), dfs(len(a) - 1, 1))
# 递推
def maxEnergyBoost2(self, a: List[int], b: List[int]) -> int:
n = len(a)
f = [[0, 0] for _ in range(n + 2)]
for i, (x, y) in enumerate(zip(a, b)):
f[i + 2][0] = max(f[i + 1][0], f[i][1]) + x
f[i + 2][1] = max(f[i + 1][1], f[i][0]) + y
return max(f[-1])