Problem Description

You have two energy drinks, A and B, represented by two integer arrays energyDrinkA and energyDrinkB of the same length n. Each element in these arrays represents the energy boost you get from drinking that energy drink at that specific hour.

Your goal is to maximize your total energy boost over n hours by drinking exactly one energy drink per hour. However, there's an important constraint: if you switch from one energy drink to the other, you must wait one hour for your system to cleanse. During this cleansing hour, you don't get any energy boost at all.

For example:

• If you drink A at hour 0 and want to switch to B at hour 1, you get 0 energy at hour 1 (cleansing hour) and can start drinking B from hour 2
• If you drink A at hour 0 and continue with A at hour 1, you get the full energy boost from A at hour 1

You can start with either energy drink A or B. The problem asks you to find the maximum total energy boost possible over all n hours.

The dynamic programming solution tracks two states at each hour:

• f[i][0]: Maximum energy boost achievable by choosing drink A at hour i
• f[i][1]: Maximum energy boost achievable by choosing drink B at hour i

At each hour, you can either:

1. Continue with the same drink from the previous hour (add current hour's energy to previous total)
2. Switch from the other drink (skip current hour's energy due to cleansing, so take only the previous hour's total from the other drink)

The final answer is the maximum between f[n-1][0] and f[n-1][1].

Intuition

The key insight is that at any given hour, we need to make a decision: which drink should we consume? This decision depends on what we did in the previous hour because of the switching penalty.

Think of this problem as making optimal choices at each step while considering the consequences of our previous choice. At each hour i, we're essentially in one of two states: either we're drinking A or we're drinking B. The crucial observation is that our maximum energy at hour i depends only on our maximum energy at hour i-1, not on the entire history of our choices.

This naturally leads to a dynamic programming approach where we track the best possible outcome for each state at each hour. For any hour i:

• If we want to drink A at hour i, we have two options:

  • We were already drinking A at hour i-1: we simply add energyDrinkA[i] to our previous total
  • We were drinking B at hour i-1: we switch, meaning we skip this hour's energy (cleansing), so we only carry forward the previous total from B

• Similarly, if we want to drink B at hour i:

  • We were already drinking B at hour i-1: add energyDrinkB[i] to our previous total
  • We were drinking A at hour i-1: switch and skip this hour's energy

The beauty of this approach is that we don't need to explicitly track when we're cleansing. The cleansing penalty is naturally incorporated when we take the maximum between continuing with the same drink (getting energy) versus switching from the other drink (no energy for this hour).

By maintaining f[i][0] and f[i][1] to represent the maximum energy when choosing drink A or B at hour i respectively, we can build up the solution hour by hour, always choosing the option that gives us the better total energy at each state.

Learn more about Dynamic Programming patterns.

Solution Approach

We use dynamic programming with a 2D array to track the maximum energy at each hour for each drink choice.

State Definition:

• f[i][0]: Maximum energy boost obtainable by choosing drink A at hour i
• f[i][1]: Maximum energy boost obtainable by choosing drink B at hour i

Initialization: At hour 0, we can start with either drink without any penalty:

• f[0][0] = energyDrinkA[0]
• f[0][1] = energyDrinkB[0]

State Transition: For each hour i from 1 to n-1, we calculate the maximum energy for each drink choice:

For choosing drink A at hour i: f[i][0] = max(f[i-1][0] + energyDrinkA[i], f[i-1][1])

• First option: Continue with A from previous hour and add current energy
• Second option: Switch from B (no energy gained this hour due to cleansing)

For choosing drink B at hour i: f[i][1] = max(f[i-1][1] + energyDrinkB[i], f[i-1][0])

• First option: Continue with B from previous hour and add current energy
• Second option: Switch from A (no energy gained this hour due to cleansing)

Implementation Details:

1. Create a 2D array f of size n × 2 to store the DP states
2. Initialize the base cases for hour 0
3. Iterate through hours 1 to n-1, applying the transition formulas
4. Return the maximum of the two final states: max(f[n-1][0], f[n-1][1])

The time complexity is O(n) as we process each hour once, and the space complexity is O(n) for storing the DP array. This could be optimized to O(1) space since we only need the previous hour's values to compute the current hour's values.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Input:

• energyDrinkA = [3, 1, 4, 2]
• energyDrinkB = [5, 2, 1, 3]
• n = 4 hours

We'll build our DP table step by step, where f[i][0] represents the maximum energy when choosing drink A at hour i, and f[i][1] represents the maximum energy when choosing drink B at hour i.

Hour 0 (Initialization):

• f[0][0] = 3 (start with drink A, get 3 energy)
• f[0][1] = 5 (start with drink B, get 5 energy)

Hour 1: For drink A at hour 1:

• Option 1: Continue with A from hour 0: f[0][0] + energyDrinkA[1] = 3 + 1 = 4
• Option 2: Switch from B (cleansing, no energy): f[0][1] = 5
• f[1][0] = max(4, 5) = 5

For drink B at hour 1:

• Option 1: Continue with B from hour 0: f[0][1] + energyDrinkB[1] = 5 + 2 = 7
• Option 2: Switch from A (cleansing, no energy): f[0][0] = 3
• f[1][1] = max(7, 3) = 7

Hour 2: For drink A at hour 2:

• Option 1: Continue with A: f[1][0] + energyDrinkA[2] = 5 + 4 = 9
• Option 2: Switch from B: f[1][1] = 7
• f[2][0] = max(9, 7) = 9

For drink B at hour 2:

• Option 1: Continue with B: f[1][1] + energyDrinkB[2] = 7 + 1 = 8
• Option 2: Switch from A: f[1][0] = 5
• f[2][1] = max(8, 5) = 8

Hour 3: For drink A at hour 3:

• Option 1: Continue with A: f[2][0] + energyDrinkA[3] = 9 + 2 = 11
• Option 2: Switch from B: f[2][1] = 8
• f[3][0] = max(11, 8) = 11

For drink B at hour 3:

• Option 1: Continue with B: f[2][1] + energyDrinkB[3] = 8 + 3 = 11
• Option 2: Switch from A: f[2][0] = 9
• f[3][1] = max(11, 9) = 11

Final Answer: max(f[3][0], f[3][1]) = max(11, 11) = 11

The optimal strategy achieves a total energy of 11. One possible sequence is: B(5) → B(2) → A(0, cleansing) → A(4) = 11 total energy. Another is: B(5) → cleansing(0) → A(4) → A(2) = 11 total energy.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the arrays energyDrinkA and energyDrinkB. The algorithm iterates through the arrays once with a single for loop from index 1 to n-1, performing constant-time operations (max comparisons and additions) at each iteration.

The space complexity is O(n). The algorithm creates a 2D array f with dimensions n × 2, which stores the dynamic programming states. This requires O(2n) = O(n) space to store the maximum energy values for each position when choosing either drink A or drink B.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Switching Penalty

Pitfall: A common mistake is thinking that switching drinks means you lose energy at the next hour after the switch, rather than at the current hour of switching.

Incorrect interpretation:

# WRONG: Penalizing the next hour
dp[i][0] = max(dp[i-1][0] + energyDrinkA[i], dp[i-1][1] + energyDrinkA[i] - penalty)

Correct interpretation:

# CORRECT: No energy gained at current hour when switching
dp[i][0] = max(dp[i-1][0] + energyDrinkA[i], dp[i-1][1])

When you switch from B to A at hour i, you get 0 energy at hour i (not energyDrinkA[i]), which is why we only take dp[i-1][1] without adding anything.

2. Space Optimization Leading to Incorrect Updates

Pitfall: When optimizing space from O(n) to O(1) by using only two variables, updating them in the wrong order can overwrite values needed for subsequent calculations.

Incorrect space optimization:

# WRONG: Overwriting prevA before it's used to calculate currB
def maxEnergyBoost(self, energyDrinkA, energyDrinkB):
    prevA = energyDrinkA[0]
    prevB = energyDrinkB[0]
  
    for i in range(1, len(energyDrinkA)):
        prevA = max(prevA + energyDrinkA[i], prevB)  # prevA updated
        prevB = max(prevB + energyDrinkB[i], prevA)  # Using the NEW prevA - WRONG!
  
    return max(prevA, prevB)

Correct space optimization:

# CORRECT: Store values in temporary variables
def maxEnergyBoost(self, energyDrinkA, energyDrinkB):
    prevA = energyDrinkA[0]
    prevB = energyDrinkB[0]
  
    for i in range(1, len(energyDrinkA)):
        currA = max(prevA + energyDrinkA[i], prevB)
        currB = max(prevB + energyDrinkB[i], prevA)
        prevA, prevB = currA, currB
  
    return max(prevA, prevB)

3. Off-by-One Errors in Hour Indexing

Pitfall: Confusion about whether the cleansing happens at hour i or hour i+1 when switching at hour i.

Example scenario causing confusion:

• Hour 0: Drink A (get energyDrinkA[0])
• Hour 1: Switch to B (get 0 energy - cleansing hour)
• Hour 2: Drink B (get energyDrinkB[2])

The key insight is that the cleansing happens at the exact hour you make the switch, not the hour after.

4. Incorrect Base Case Initialization

Pitfall: Initializing both drinks at hour 0 with 0 or forgetting that you must choose one drink to start.

Incorrect initialization:

# WRONG: Starting with 0 energy
dp[0][0] = 0
dp[0][1] = 0

Correct initialization:

# CORRECT: You must drink something at hour 0
dp[0][0] = energyDrinkA[0]
dp[0][1] = energyDrinkB[0]

The problem states you drink exactly one energy drink per hour, so at hour 0, you must choose either A or B and gain its energy.