# Maximum Energy Boost From Two Drinks
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-energy-boost-from-two-drinks)
Canonical: https://scaleengineer.com/dsa/problems/maximum-energy-boost-from-two-drinks
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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 <= 105`
* `1 <= energyDrinkA[i], energyDrinkB[i] <= 105`

# Approaches
## Dynamic Programming with Memoization (Top-Down)
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.
**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`.
**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 `StackOverflowError` for very large `n` due to deep recursion, although the constraints `n <= 10^5` are usually handled by modern JVMs.
### Explanation
We can model the problem by defining two states for each hour `i`:
1. The maximum energy boost accumulated up to hour `i`, with the last drink being A.
2. 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.

```java
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);
    }
}
```
### Algorithm
- Define two mutually recursive functions, `findMaxA(i)` and `findMaxB(i)`, to compute the maximum energy up to hour `i` ending with drink A and B, respectively.
- Use two memoization arrays, `memoA` and `memoB`, 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 for `i=0` is also handled explicitly.
- The recursive step for `findMaxA(i)` is `energyDrinkA[i] + max(findMaxA(i-1), findMaxB(i-2))`. A similar relation holds for `findMaxB(i)`.
- If a result for `findMaxA(i)` or `findMaxB(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))`.

## 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.
**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.
**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.
### Explanation
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]`.

```java
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]);
    }
}
```
### 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])`.

## Space-Optimized Dynamic Programming
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).
**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`.
**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.
### Explanation
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 hour `i-1`.
- `dpA_prev2`: Max energy ending with A at hour `i-2`.
- `dpB_prev1`: Max energy ending with B at hour `i-1`.
- `dpB_prev2`: Max energy ending with B at hour `i-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`.

```java
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);
    }
}
```
### Algorithm
- Observe that the calculation for hour `i` only depends on the results from hours `i-1` and `i-2`.
- Instead of full arrays, use a few variables to store the previous two states for both `dpA` and `dpB`.
- Let `dpA_prev1` and `dpA_prev2` store the values for `dpA[i-1]` and `dpA[i-2]` respectively. Similarly for `dpB`.
- Initialize these variables with the values for `i=0` and `i=1`.
- Iterate from `i = 2` to `n-1`.
- In each iteration, calculate the current values, `dpA_curr` and `dpB_curr`, using the `_prev1` and `_prev2` variables.
- After calculation, update the `prev` variables for the next iteration: `_prev2` gets the value of `_prev1`, and `_prev1` gets the value of `_curr`.
- After the loop, the answer is `max(dpA_prev1, dpB_prev1)`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

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

```