Problem Description

You are given two integer arrays energyDrinkA and energyDrinkB, each of length n, representing the energy boosts per hour provided by two different energy drinks, A and B, respectively. To maximize your total energy boost, you can drink one energy drink per hour. However, switching from one energy drink to the other requires waiting for one hour to cleanse your system, during which you won't receive any energy boost. You can start with either of the two energy drinks. Return the maximum total energy boost achievable in the next n hours.

Intuition

To solve this problem, we use a dynamic programming approach. We define f[i][0] as the maximum energy boost obtained up to hour i when drinking energy drink A at that hour, and f[i][1] as the maximum energy boost obtained up to hour i when drinking energy drink B at that hour.

The key challenge is to balance between the energy boost obtained by consistently drinking the same energy drink and the potential benefit of switching drinks, despite the one-hour penalty.

We initialize:

• f[0][0] with the energy boost from energyDrinkA[0].
• f[0][1] with the energy boost from energyDrinkB[0].

The state transitions are defined as follows for each hour i from 1 to n-1:

• f[i][0] is the maximum of continuing with drink A (f[i-1][0] + energyDrinkA[i]) or switching from drink B (f[i-1][1] because of the penalty hour).
• f[i][1] is the maximum of continuing with drink B (f[i-1][1] + energyDrinkB[i]) or switching from drink A (f[i-1][0]).

Finally, the result is the maximum value between f[n-1][0] and f[n-1][1], representing the best possible total energy boost achievable by the end of the n hours.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution is implemented using a dynamic programming approach. We utilize a 2D list f to keep track of the maximum energy boost achievable up to each hour i, with separate entries for choosing energy drink A or B at that hour.

1. Initialization:

   • Create a 2D list f with n rows and 2 columns, each initialized to 0. This will store the maximum energy boost for each hour i using either drink A or drink B.
   • Set f[0][0] to energyDrinkA[0], representing the initial choice of drink A.
   • Set f[0][1] to energyDrinkB[0], representing the initial choice of drink B.

2. State Transitions:

   • For each hour i from 1 to n-1, compute:
     • f[i][0] as max(f[i - 1][0] + energyDrinkA[i], f[i - 1][1]): the maximum energy boost by either continuing with drink A from the previous hour or switching from drink B after a one-hour wait.
     • f[i][1] as max(f[i - 1][1] + energyDrinkB[i], f[i - 1][0]): similarly, the maximum energy boost by either continuing with drink B from the previous hour or switching from drink A after a one-hour wait.

3. Result:

   • Return max(f[n - 1][0], f[n - 1][1]) to retrieve the highest energy boost possible by the end of n hours.

Here's the code implementing the approach:

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])

This algorithm efficiently computes the maximum possible energy boost by dynamically deciding whether to switch drinks or continue with the current choice, considering the penalty for switching.

Example Walkthrough

Let's walk through the solution approach using a small example. Assume energyDrinkA = [3, 2, 7] and energyDrinkB = [4, 5, 1].

1. Initialization:

   • Length of the arrays, n = 3.
   • Create a 2D list f with dimensions 3 x 2. Initially, f is [[0, 0], [0, 0], [0, 0]].
   • Set the base cases:
     • f[0][0] = energyDrinkA[0] = 3
     • f[0][1] = energyDrinkB[0] = 4
     • So, f is now [[3, 4], [0, 0], [0, 0]].

2. State Transitions:

   • For hour 1 (i = 1):
     • f[1][0] = max(f[0][0] + energyDrinkA[1], f[0][1]) = max(3 + 2, 4) = max(5, 4) = 5
     • f[1][1] = max(f[0][1] + energyDrinkB[1], f[0][0]) = max(4 + 5, 3) = max(9, 3) = 9
     • f becomes [[3, 4], [5, 9], [0, 0]].
   • For hour 2 (i = 2):
     • f[2][0] = max(f[1][0] + energyDrinkA[2], f[1][1]) = max(5 + 7, 9) = max(12, 9) = 12
     • f[2][1] = max(f[1][1] + energyDrinkB[2], f[1][0]) = max(9 + 1, 5) = max(10, 5) = 10
     • f updates to [[3, 4], [5, 9], [12, 10]].

3. Result:

   • The maximum total energy boost achievable in the next 3 hours is max(f[2][0], f[2][1]) = max(12, 10) = 12.

Therefore, the maximum energy boost achievable is 12 units.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n) because it involves a single loop that iterates through the list from start to finish, where n is the length of the input arrays energyDrinkA and energyDrinkB. Each iteration involves constant-time operations.

The space complexity of the code is O(n) due to the 2D list f created to store intermediate results. This list requires space proportional to n, with two entries per element to track the maximum energy boost for selecting either energyDrinkA[i] or energyDrinkB[i] at each step.

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