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] <= 105This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Dynamic Programming Solution | Time Complexity: O(n) |
| Greedy Approach with Pruning | Time Complexity: O(n) |
How to EASILY solve LeetCode problems • NeetCode • 427,763 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