You are given two integer arrays energyDrinkA and energyDrinkB of the same length n by a futuristic sports scientist. These arrays represent the energy boosts per hour provided by two different energy drinks, A and B, respectively.
You want to maximize your total energy boost by drinking one energy drink per hour. However, if you want to switch from consuming one energy drink to the other, you need to wait for one hour to cleanse your system (meaning you won't get any energy boost in that hour).
Return the maximum total energy boost you can gain in the next n hours.
Note that you can start consuming either of the two energy drinks.
Example 1:
Input: energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
Output: 5
Explanation:
To gain an energy boost of 5, drink only the energy drink A (or only B).
Example 2:
Input: energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
Output: 7
Explanation:
To gain an energy boost of 7:
Constraints:
n == energyDrinkA.length == energyDrinkB.length3 <= n <= 1051 <= energyDrinkA[i], energyDrinkB[i] <= 105Problem Overview: You are given two arrays where A[i] and B[i] represent the energy gained from two different drinks at hour i. You can drink only one per hour. Switching drinks forces a one‑hour cooldown where no energy is gained. The goal is to maximize the total energy collected across all hours.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
This problem naturally fits dynamic programming. Track two states: the best energy if the current hour ends with drink A or drink B. Let dpA[i] be the maximum energy achievable up to hour i when drinking A at that hour, and dpB[i] the equivalent for drink B. Continuing the same drink simply adds the current energy (dpA[i-1] + A[i]). Switching requires skipping one hour due to the cooldown, so the transition becomes dpB[i-2] + A[i] (and vice versa). Iterate through the array, updating both states at every step. The answer is max(dpA[n-1], dpB[n-1]). This approach systematically evaluates both choices at every hour and guarantees the optimal total. Time complexity is O(n) because each index is processed once, and space complexity is O(n) for the DP arrays.
Approach 2: Greedy with Pruning (O(n) time, O(1) space)
A more space‑efficient variation observes that each state depends only on the previous one or two hours. Instead of storing full DP arrays, keep rolling variables representing the best totals for the last two positions for each drink. At each step, compute the gain for continuing the same drink or switching after the cooldown, then keep only the maximum candidate. Greedy pruning discards dominated states where continuing or switching would always produce a smaller total than another tracked option. Because only constant state is maintained, the algorithm runs in O(n) time with O(1) extra space. This version is preferred when memory usage matters or when implementing a concise interview solution.
Recommended for interviews: The dynamic programming formulation is the expected explanation because it clearly models the cooldown constraint and state transitions. Writing the full DP first demonstrates solid reasoning about state definition and recurrence. After that, optimizing to rolling variables (the greedy‑pruned version) shows deeper understanding of DP space reduction.
This approach involves using dynamic programming to track the maximum energy boost at each hour when choosing between continuing with the current drink or switching to the other, accounting for the necessary hour idle when switching.
The C solution uses two arrays, dpA and dpB, where dpA[i] and dpB[i] represent the maximum energy boost possible up to hour i using drink A and B respectively. The state transition considers whether to continue with the same drink or switch while accounting for the loss of energy boost when switching.
Time Complexity: O(n)
Space Complexity: O(n)
This approach uses a greedy method to consider maximum energy at each point and prune the possibility of switching drinks smartly to avoid unnecessary calculations. It initiates from collecting max energy without switching and checks switch influence cautiously without calculating every possibility.
This C solution introduces a greedy technique where we evaluate the total energies obtained at each hour without switching and decide on when to assess the outcome of switching. It reduces unnecessary operations by focusing on possible beneficial switches rather than every potential switch point.
Time Complexity: O(n)
Space Complexity: O(1)
We define f[i][0] to represent the maximum boost energy obtained by choosing energy drink A at the i-th hour, and f[i][1] to represent the maximum boost energy obtained by choosing energy drink B at the i-th hour. Initially, f[0][0] = energyDrinkA[0], f[0][1] = energyDrinkB[0]. The answer is max(f[n - 1][0], f[n - 1][1]).
For i > 0, we have the following state transition equations:
$
\begin{aligned}
f[i][0] & = max(f[i - 1][0] + energyDrinkA[i], f[i - 1][1]) \
f[i][1] & = max(f[i - 1][1] + energyDrinkB[i], f[i - 1][0])
\end{aligned}
Finally, return max(f[n - 1][0], f[n - 1][1]).
The time complexity is O(n), and the space complexity is O(n). Here, n$ is the length of the array.
Python
Java
C++
Go
TypeScript
We notice that the state f[i] is only related to f[i - 1] and not to f[i - 2]. Therefore, we can use only two variables f and g to maintain the state, thus optimizing the space complexity to O(1).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Solution | Time Complexity: O(n) |
| Greedy Approach with Pruning | Time Complexity: O(n) |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n) | O(n) | Best for explaining the recurrence and cooldown transition clearly in interviews |
| Greedy with Pruning (Rolling DP) | O(n) | O(1) | When optimizing memory or implementing a concise production solution |
3259 Maximum Energy Boost From Two Drinks || How to 🤔 in Interview || Top Down (Memo) + Bottom Up 🔥 • Ayush Rao • 993 views views
Watch 9 more video solutions →Practice Maximum Energy Boost From Two Drinks with our built-in code editor and test cases.
Practice on FleetCode