Maximum Energy Boost From Two Drinks
MedPrompt
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:
- Drink the energy drink A for the first hour.
- Switch to the energy drink B and we lose the energy boost of the second hour.
- Gain the energy boost of the drink B in the third hour.
Constraints:
n == energyDrinkA.length == energyDrinkB.length3 <= n <= 1051 <= energyDrinkA[i], energyDrinkB[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses tabulation, a bottom-up dynamic programming technique. We build the solution iteratively from the smallest subproblems. We use two arrays to store the maximum energy achievable at each hour for each type of drink. This avoids recursion and its associated overhead.
Algorithm
- Create two DP arrays,
dpAanddpB, of sizen. dpA[i]will store the maximum energy boost up to houri, ending with drink A.dpB[i]will store the maximum energy boost up to houri, ending with drink B.- Initialize the base cases for
i=0andi=1.dpA[0] = energyDrinkA[0],dpB[0] = energyDrinkB[0]dpA[1] = energyDrinkA[1] + dpA[0],dpB[1] = energyDrinkB[1] + dpB[0]
- Iterate from
i = 2ton-1and fill the DP tables using the recurrence relations:dpA[i] = energyDrinkA[i] + max(dpA[i-1], dpB[i-2])dpB[i] = energyDrinkB[i] + max(dpB[i-1], dpA[i-2])
- The final answer is
max(dpA[n-1], dpB[n-1]).
Walkthrough
We define two arrays, dpA and dpB, where dpA[i] stores the maximum possible energy boost after i+1 hours (from hour 0 to i), ending with consumption of energyDrinkA at hour i. dpB[i] is defined similarly for energyDrinkB.
The base cases are for the first two hours (i=0 and i=1).
For i=0, we can only start with one drink: dpA[0] = energyDrinkA[0] and dpB[0] = energyDrinkB[0].
For i=1, we can only continue with the same drink, as a switch requires two hours: dpA[1] = energyDrinkA[1] + dpA[0] and dpB[1] = energyDrinkB[1] + dpB[0].
For any subsequent hour i >= 2, we can calculate dpA[i] by taking the energy from energyDrinkA[i] and adding the maximum energy from the previous state. The previous state could be either continuing with A (max energy dpA[i-1]) or switching from B (max energy dpB[i-2], as hour i-1 is for cleansing). We take the maximum of these two possibilities. The same logic applies to dpB[i].
After filling the arrays up to n-1, the maximum total energy is the maximum of dpA[n-1] and dpB[n-1].
class Solution { public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) { int n = energyDrinkA.length; // As per constraints, n >= 3. long[] dpA = new long[n]; long[] dpB = new long[n]; // Base case: i = 0 dpA[0] = energyDrinkA[0]; dpB[0] = energyDrinkB[0]; // Base case: i = 1 dpA[1] = energyDrinkA[1] + dpA[0]; dpB[1] = energyDrinkB[1] + dpB[0]; // Fill DP table for i from 2 to n-1 for (int i = 2; i < n; i++) { dpA[i] = energyDrinkA[i] + Math.max(dpA[i - 1], dpB[i - 2]); dpB[i] = energyDrinkB[i] + Math.max(dpB[i - 1], dpA[i - 2]); } return Math.max(dpA[n - 1], dpB[n - 1]); }}Complexity
Time
O(n) - We iterate through the arrays once with a single loop.
Space
O(n) - Two arrays of size `n` are used to store the DP states.
Trade-offs
Pros
Efficient O(n) time complexity.
Avoids recursion overhead, which can make it slightly faster in practice than the memoization approach.
The iterative nature is often easier to reason about and debug.
Cons
Requires O(n) extra space, which might be a concern for extremely large inputs, although it's acceptable for the given constraints.
This is the most efficient approach, optimizing the space complexity of the iterative DP solution. By noticing that the state at any hour i only depends on the states at i-1 and i-2, we can discard the older states and use only a constant number of variables to keep track of the necessary information. This reduces the space complexity from O(n) to O(1).
Algorithm
- Observe that the calculation for hour
ionly depends on the results from hoursi-1andi-2. - Instead of full arrays, use a few variables to store the previous two states for both
dpAanddpB. - Let
dpA_prev1anddpA_prev2store the values fordpA[i-1]anddpA[i-2]respectively. Similarly fordpB. - Initialize these variables with the values for
i=0andi=1. - Iterate from
i = 2ton-1. - In each iteration, calculate the current values,
dpA_curranddpB_curr, using the_prev1and_prev2variables. - After calculation, update the
prevvariables for the next iteration:_prev2gets the value of_prev1, and_prev1gets the value of_curr. - After the loop, the answer is
max(dpA_prev1, dpB_prev1).
Walkthrough
This approach builds upon the bottom-up DP logic. The key observation is that dpA[i] depends only on dpA[i-1] and dpB[i-2], and dpB[i] depends only on dpB[i-1] and dpA[i-2]. This means we don't need to store the entire history of DP values. We only need to remember the results from the last two hours.
We can use four variables to track these states:
dpA_prev1: Max energy ending with A at houri-1.dpA_prev2: Max energy ending with A at houri-2.dpB_prev1: Max energy ending with B at houri-1.dpB_prev2: Max energy ending with B at houri-2.
We first compute the values for i=0 and i=1 to initialize our variables. Then, we loop from i=2 to n-1. In each iteration, we compute the current max energy for A and B using the prev1 and prev2 variables. After that, we update the prev variables to slide the window forward for the next iteration. The final result will be the maximum of the variables holding the state for hour n-1.
class Solution { public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) { int n = energyDrinkA.length; // As per constraints, n >= 3. // Initialize states for i=0 (which will become i-2 in the first loop iteration) long dpA_prev2 = energyDrinkA[0]; long dpB_prev2 = energyDrinkB[0]; // Initialize states for i=1 (which will become i-1 in the first loop iteration) long dpA_prev1 = energyDrinkA[1] + dpA_prev2; long dpB_prev1 = energyDrinkB[1] + dpB_prev2; // Iterate from i = 2 to n-1 for (int i = 2; i < n; i++) { long dpA_curr = energyDrinkA[i] + Math.max(dpA_prev1, dpB_prev2); long dpB_curr = energyDrinkB[i] + Math.max(dpB_prev1, dpA_prev2); // Update variables for the next iteration dpA_prev2 = dpA_prev1; dpB_prev2 = dpB_prev1; dpA_prev1 = dpA_curr; dpB_prev1 = dpB_curr; } return Math.max(dpA_prev1, dpB_prev1); }}Complexity
Time
O(n) - A single pass is made through the input arrays.
Space
O(1) - We only use a constant number of variables to store the previous states, regardless of the input size `n`.
Trade-offs
Pros
Optimal O(1) space complexity, making it highly memory-efficient.
Optimal O(n) time complexity.
Cons
The code can be slightly harder to write and debug compared to the version with full DP arrays, as state management is manual.
This approach uses recursion with memoization, which is a top-down dynamic programming technique. We define a recurrence relation for the maximum energy boost and use a helper data structure (like an array or map) to cache the results of subproblems. This prevents re-computation of the same subproblem, thus optimizing the time complexity from exponential to linear.
Algorithm
- Define two mutually recursive functions,
findMaxA(i)andfindMaxB(i), to compute the maximum energy up to houriending with drink A and B, respectively. - Use two memoization arrays,
memoAandmemoB, to store the results of these function calls to avoid redundant computations. - The base case for the recursion is at
i < 0, where the energy is 0. The case fori=0is also handled explicitly. - The recursive step for
findMaxA(i)isenergyDrinkA[i] + max(findMaxA(i-1), findMaxB(i-2)). A similar relation holds forfindMaxB(i). - If a result for
findMaxA(i)orfindMaxB(i)is already in the memoization table, return it directly. Otherwise, compute it, store it, and then return it. - The final answer is
max(findMaxA(n-1), findMaxB(n-1)).
Walkthrough
We can model the problem by defining two states for each hour i:
- The maximum energy boost accumulated up to hour
i, with the last drink being A. - The maximum energy boost accumulated up to hour
i, with the last drink being B.
Let's define findMaxA(i) and findMaxB(i) as two recursive functions that calculate these values. To get the maximum energy ending with drink A at hour i, we must have either continued with drink A from hour i-1 or switched from drink B. A switch from B to A requires drinking B at i-2 and cleansing at i-1. Therefore, the recurrence relation is:
findMaxA(i) = energyDrinkA[i] + max(findMaxA(i-1), findMaxB(i-2))
findMaxB(i) = energyDrinkB[i] + max(findMaxB(i-1), findMaxA(i-2))
To avoid the exponential complexity of pure recursion, we store the results of findMaxA(i) and findMaxB(i) in memoization arrays (memoA and memoB). Before computing a value, we check if it's already been memoized. If so, we return the stored value. Otherwise, we compute, store, and return it.
class Solution { long[] memoA; long[] memoB; int[] energyDrinkA; int[] energyDrinkB; int n; public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) { this.n = energyDrinkA.length; this.energyDrinkA = energyDrinkA; this.energyDrinkB = energyDrinkB; this.memoA = new long[n]; this.memoB = new long[n]; java.util.Arrays.fill(memoA, -1); java.util.Arrays.fill(memoB, -1); return Math.max(findMaxA(n - 1), findMaxB(n - 1)); } private long findMaxA(int i) { if (i < 0) return 0; if (memoA[i] != -1) return memoA[i]; if (i == 0) { return memoA[i] = energyDrinkA[0]; } long continueA = findMaxA(i - 1); long switchToA = findMaxB(i - 2); return memoA[i] = energyDrinkA[i] + Math.max(continueA, switchToA); } private long findMaxB(int i) { if (i < 0) return 0; if (memoB[i] != -1) return memoB[i]; if (i == 0) { return memoB[i] = energyDrinkB[0]; } long continueB = findMaxB(i - 1); long switchToB = findMaxA(i - 2); return memoB[i] = energyDrinkB[i] + Math.max(continueB, switchToB); }}Complexity
Time
O(n) - Each of the `2*n` states (`(i, A)` and `(i, B)` for `i` from 0 to `n-1`) is computed exactly once.
Space
O(n) - We use two arrays of size `n` for memoization. The recursion stack depth can also go up to `n`.
Trade-offs
Pros
Guarantees an optimal solution with a significant performance improvement over brute-force recursion.
The code structure closely follows the mathematical recurrence relation, making it intuitive to write.
Cons
Uses O(n) extra space for the memoization tables.
May lead to a
StackOverflowErrorfor very largendue to deep recursion, although the constraintsn <= 10^5are usually handled by modern JVMs.
Solutions
Solution
class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) { int n = energyDrinkA.length; long[][] f = new long[n][2]; f[0][0] = energyDrinkA[0]; f[0][1] = energyDrinkB[0]; for (int i = 1; i < n; ++i) { f[i][0] = Math.max(f[i - 1][0] + energyDrinkA[i], f[i - 1][1]); f[i][1] = Math.max(f[i - 1][1] + energyDrinkB[i], f[i - 1][0]); } return Math.max(f[n - 1][0], f[n - 1][1]); }}class Solution {public: long long maxEnergyBoost(vector<int> &energyDrinkA, vector<int> &energyDrinkB) { int n = energyDrinkA.size(); vector<vector<long long>> f(n, vector<long long>(2)); f[0][0] = energyDrinkA[0]; f[0][1] = energyDrinkB[0]; for (int i = 1; i < n; ++i) { 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]); } return max(f[n - 1][0], f[n - 1][1]); }};class Solution: def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int: n = len(energyDrinkA) f = [[0] * 2 for _ in range(n)] f[0][0] = energyDrinkA[0] f[0][1] = energyDrinkB[0] for i in range(1, n): 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]) return max(f[n - 1])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.