Maximum Energy Boost From Two Drinks

MEDIUM

Description

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.length
3 <= n <= 10⁵
1 <= energyDrinkA[i], energyDrinkB[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Maximum Energy Boost From Two Drinks. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming with Tabulation (Bottom-Up)

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, dpA and dpB, of size n.
dpA[i] will store the maximum energy boost up to hour i, ending with drink A.
dpB[i] will store the maximum energy boost up to hour i, ending with drink B.
Initialize the base cases for i=0 and i=1.
- dpA[0] = energyDrinkA[0], dpB[0] = energyDrinkB[0]
- dpA[1] = energyDrinkA[1] + dpA[0], dpB[1] = energyDrinkB[1] + dpB[0]
Iterate from i = 2 to n-1 and 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]).

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 Analysis

Time Complexity: O(n) - We iterate through the arrays once with a single loop.Space Complexity: O(n) - Two arrays of size `n` are used to store the DP states.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Energy Boost From Two Drinks. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Maximum Energy Boost From Two Drinks

Patterns:

Dynamic Programming

Data Structures:

Array