We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Energy Boost From Two Drinks

Number: 3525

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

You are given two arrays, energyDrinkA and energyDrinkB, each of length n. Each element represents the energy boost granted by that drink during a particular hour. In every hour you must either drink one of the drinks or, if you decide to switch from one drink type to the other, you’re forced to spend that hour cleansing your system (i.e. obtaining 0 energy). The goal is to plan your schedule over the n hours to maximize the total energy boost. You can start with either drink.

Key Insights

  • You have a fixed number of hours in which each hour you perform one of two actions: drink from one of the two drinks or cleanse your system.
  • Continuing to drink the same type in consecutive hours incurs no penalty.
  • When switching from one drink to the other, a “cleansing” hour (with 0 energy boost) must be inserted.
  • A dynamic programming approach is ideal where different states track whether you are in a drinking state (and which drink you last consumed) or in a cleansing state.
  • Transitions:
    • From drinking the same drink: simply add the current hour’s energy.
    • From a cleansing hour: you may start drinking from either energy drink.
    • At any hour, you have the option to cleanse (which might be useful if you plan to switch drinks later).

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (this can be optimized to O(1) by storing only the previous state)

Solution

We use a state machine approach with dynamic programming. Define three states for each hour i: • dpA[i]: Maximum energy obtained up to hour i when you drink energy drink A at hour i.
• dpB[i]: Maximum energy obtained up to hour i when you drink energy drink B at hour i.
• dpC[i]: Maximum energy obtained up to hour i when you decide to cleanse (i.e. not drink) at hour i.

Base case:
• At hour 0, you can choose to drink A or B. Thus, dpA[0] = energyDrinkA[0] and dpB[0] = energyDrinkB[0]. You might also opt to cleanse even in the first hour (yielding 0).

For each subsequent hour (i from 1 to n-1), the transitions are:

  1. If drinking A:
    • Continue with A: dpA[i] = dpA[i-1] + energyDrinkA[i].
    • If coming from cleansing: dpA[i] = dpC[i-1] + energyDrinkA[i].
    • Take the maximum of these.
  2. Similarly for drinking B.
  3. If you decide to cleanse at hour i:
    • dpC[i] = max(dpA[i-1], dpB[i-1], dpC[i-1]).

Finally, the answer is the maximum value among dpA[n-1], dpB[n-1], and dpC[n-1].

The key idea is that once you decide to switch the drink type, you must intentionally “skip” an hour (cleansing hour) which is modeled by the dpC state.

Code Solutions

# Python solution with line-by-line comments

def maxEnergyBoost(energyDrinkA, energyDrinkB):
    n = len(energyDrinkA)
    # Initialize dp arrays for drinking A, drinking B, and cleansing.
    dpA = [0] * n  # dpA[i] holds max energy ending at hour i with drink A
    dpB = [0] * n  # dpB[i] holds max energy ending at hour i with drink B
    dpC = [0] * n  # dpC[i] holds max energy ending at hour i with cleansing (no drink)
    
    # Base cases: for hour 0
    dpA[0] = energyDrinkA[0]   # if you choose drink A at hour 0
    dpB[0] = energyDrinkB[0]   # if you choose drink B at hour 0
    dpC[0] = 0               # cleansing yields 0 energy
    
    # Compute dp values for each subsequent hour
    for i in range(1, n):
        # Option to drink A:
        # Either continue from previous A drinking or start drinking A after cleansing
        dpA[i] = max(dpA[i-1] + energyDrinkA[i], dpC[i-1] + energyDrinkA[i])
        
        # Option to drink B:
        dpB[i] = max(dpB[i-1] + energyDrinkB[i], dpC[i-1] + energyDrinkB[i])
        
        # Option to cleanse:
        dpC[i] = max(dpA[i-1], dpB[i-1], dpC[i-1])
    
    # The answer is the maximum energy attainable at the final hour
    return max(dpA[n-1], dpB[n-1], dpC[n-1])

# Example usage:
print(maxEnergyBoost([4,1,1], [1,1,3]))  # Expected output: 7
← Back to All Questions