Maximum Energy Boost From Two Drinks — Problem & Solution
Maximum Energy Boost From Two Drinks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Energy Boost From Two Drinks is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two arrays of length n, energyDrinkA and energyDrinkB, give the energy boost each drink provides in each of the next n hours.
Every hour you drink one of the two, starting with either. To switch from one drink to the other you must spend one hour cleansing your system, gaining nothing that hour.
Return the maximum total energy boost over the n hours.
CodeKairo bound: boosts are at most 10^4 (LeetCode allows 10^5) so that the total fits in a 32-bit integer.
Example 1
Input: energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
Output: 5
Explanation: Drink only A (1 + 3 + 1) or only B (3 + 1 + 1).
Example 2
Input: energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
Output: 7
Explanation: A in hour 0, cleanse in hour 1, B in hour 2.
Example 3
Input: energyDrinkA = [2,2,9,1], energyDrinkB = [5,5,1,1]
Output: 15
Explanation: B, cleanse, A, A: 5 + 9 + 1.
Constraints
n == energyDrinkA.length == energyDrinkB.length3 <= n <= 10^51 <= energyDrinkA[i], energyDrinkB[i] <= 10^4
Hints for Maximum Energy Boost From Two Drinks
Hint 1
Track the best total that ends with each drink at hour
i.Hint 2
To drink A at hour
i, the previous hour was either A, or a cleansing hour after B at houri - 2.Hint 3
a[i] = max(a[i-1], b[i-2]) + A[i]and symmetrically forb[i].
How to solve Maximum Energy Boost From Two Drinks
Two-state DP. A switch costs exactly one hour, so the hour before an A-drink is either another A-drink or the cleanse that followed a B-drink two hours earlier.
Approach
a[0] = A[0],b[0] = B[0]; treata[-1] = b[-1] = 0.- For
i >= 1:a[i] = max(a[i-1], b[i-2]) + A[i],b[i] = max(b[i-1], a[i-2]) + B[i]. - Return
max(a[n-1], b[n-1]); only the last two values of each are ever needed.
Why it works
In an optimal plan the hour before drinking A at hour i either holds an A-drink (continue) or is a cleanse; a cleanse is only ever worth taking to switch, so the hour before it holds a B-drink. Both predecessors are optimal sub-plans, so the recurrence is exact (an unnecessary idle hour never helps because every boost is positive).
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Switching does not cost the next drink — it costs one whole hour of boost.
- You may start with either drink; do not force a start with A.
- With LeetCode's original bounds the total needs 64 bits; the tightened bound keeps it in 32.
Reference solution
Python
from typing import List
def maxEnergyBoost(energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
a, b = energyDrinkA, energyDrinkB
pa = pb = 0
ca, cb = a[0], b[0]
for i in range(1, len(a)):
na = max(ca, pb) + a[i]
nb = max(cb, pa) + b[i]
pa, pb = ca, cb
ca, cb = na, nb
return max(ca, cb)Java
public static int maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
int pa = 0, pb = 0;
int ca = energyDrinkA[0], cb = energyDrinkB[0];
for (int i = 1; i < energyDrinkA.length; i++) {
int na = Math.max(ca, pb) + energyDrinkA[i];
int nb = Math.max(cb, pa) + energyDrinkB[i];
pa = ca; pb = cb;
ca = na; cb = nb;
}
return Math.max(ca, cb);
}C++
int maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
int pa = 0, pb = 0;
int ca = energyDrinkA[0], cb = energyDrinkB[0];
for (size_t i = 1; i < energyDrinkA.size(); i++) {
int na = max(ca, pb) + energyDrinkA[i];
int nb = max(cb, pa) + energyDrinkB[i];
pa = ca; pb = cb;
ca = na; cb = nb;
}
return max(ca, cb);
}JavaScript
var maxEnergyBoost = function(energyDrinkA, energyDrinkB) {
var pa = 0, pb = 0;
var ca = energyDrinkA[0], cb = energyDrinkB[0];
for (var i = 1; i < energyDrinkA.length; i++) {
var na = Math.max(ca, pb) + energyDrinkA[i];
var nb = Math.max(cb, pa) + energyDrinkB[i];
pa = ca; pb = cb;
ca = na; cb = nb;
}
return Math.max(ca, cb);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming