<p>You are given two integer arrays <code>energyDrinkA</code> and <code>energyDrinkB</code> of the same length <code>n</code> by a futuristic sports scientist. These arrays represent the energy boosts per hour provided by two different energy drinks, A and B, respectively.</p>

<p>You want to <em>maximize</em> your total energy boost by drinking one energy drink <em>per hour</em>. However, if you want to switch from consuming one energy drink to the other, you need to wait for <em>one hour</em> to cleanse your system (meaning you won&#39;t get any energy boost in that hour).</p>

<p>Return the <strong>maximum</strong> total energy boost you can gain in the next <code>n</code> hours.</p>

<p><strong>Note</strong> that you can start consuming <em>either</em> of the two energy drinks.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> energyDrinkA<span class="example-io"> = [1,3,1], </span>energyDrinkB<span class="example-io"> = [3,1,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p>To gain an energy boost of 5, drink only the energy drink A (or only B).</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> energyDrinkA<span class="example-io"> = [4,1,1], </span>energyDrinkB<span class="example-io"> = [1,1,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">7</span></p>

<p><strong>Explanation:</strong></p>

<p>To gain an energy boost of 7:</p>

<ul>
	<li>Drink the energy drink A for the first hour.</li>
	<li>Switch to the energy drink B and we lose the energy boost of the second hour.</li>
	<li>Gain the energy boost of the drink B in the third hour.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == energyDrinkA.length == energyDrinkB.length</code></li>
	<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= energyDrinkA[i], energyDrinkB[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        # heapq._heapify_max(energyDrinkA)
        # heapq._heapify_max(energyDrinkB)
        # maxA = heapq._heappop_max(energyDrinkA)
        # maxB = heapq._heappop_max(energyDrinkB)
        
        # gain = 0
        # n = len(energyDrinkA)
        # side = True #true is for A and False is for b
        # if maxA < maxB:
        #     side = False
        # i = 0
        # while i < n:
        #     print(gain, side, maxA, maxB)
        #     if maxA >= (maxB / 2) and side: #a is greater and side is A currently
        #         gain += maxA
        #         maxA = heapq._heappop_max(energyDrinkA)
        #         i += 1
        #     elif (maxB / 2) > maxA and side:
        #         side = False
        #         gain += maxB
        #         maxB = heapq._heappop_max(energyDrinkB)
        #         i += 2
        #     elif (maxA / 2) > (maxB) and not side: #a is greater and side is B currently
        #         gain += maxA
        #         side = True
        #         maxA = heapq._heappop_max(energyDrinkA)
        #         i += 2
        #     elif maxB >= (maxA / 2) and not side:
        #         gain += maxB
        #         maxB = heapq._heappop_max(energyDrinkB)
        #         i += 1
            
        # return gain
        # def solve_a(i, currSum, drink):
        #     if i >= n or i >= n:
        #         return currSum
        #     currSum += drink[i]
        #     no_switch = solve_a(i + 1, currSum, energyDrinkA)
        #     switch = solve_a(i + 2, currSum , energyDrinkB)
        #     return max(switch, no_switch)
        # def solve_b(i, currSum, drink):
        #     if i >= n or i >= n:
        #         return currSum
        #     currSum += drink[i]
        #     no_switch = solve_b(i + 1,  currSum, energyDrinkB)
        #     switch = solve_b(i + 2, currSum,  energyDrinkA)
        #     return max(switch, no_switch)
        memo = {}
        n = len(energyDrinkA)
        
        def solve(i, sameDrink, diffDrink, same):
            if i >= n:
                return 0
            if (i, same) in memo:
                return memo[(i, same)]
            
            # Continue with the same drink
            no_switch = sameDrink[i] + solve(i + 1, sameDrink, diffDrink, same)
            
            # Switch to the other drink (skip one hour)
            switch = 0
            if i + 1 < n:
                switch = solve(i + 2, diffDrink, sameDrink, not same) + diffDrink[i + 1]
            
            memo[(i, same)] = max(no_switch, switch)
            return memo[(i, same)]
        
        # Start with either drink A or drink B
        return max(solve(0, energyDrinkA, energyDrinkB, True), solve(0, energyDrinkB, energyDrinkA, False))

334159