3259. Maximum Energy Boost From Two Drinks Solution

The 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 <= 10⁵
1 <= energyDrinkA[i], energyDrinkB[i] <= 10⁵

Approach overview

Problem Overview: You are given two arrays where A[i] and B[i] represent the energy gained from two different drinks at hour i. You can drink only one per hour. Switching drinks forces a one‑hour cooldown where no energy is gained. The goal is to maximize the total energy collected across all hours.

Approach 1: Dynamic Programming (O(n) time, O(n) space)

This problem naturally fits dynamic programming. Track two states: the best energy if the current hour ends with drink A or drink B. Let dpA[i] be the maximum energy achievable up to hour i when drinking A at that hour, and dpB[i] the equivalent for drink B. Continuing the same drink simply adds the current energy (dpA[i-1] + A[i]). Switching requires skipping one hour due to the cooldown, so the transition becomes dpB[i-2] + A[i] (and vice versa). Iterate through the array, updating both states at every step. The answer is max(dpA[n-1], dpB[n-1]). This approach systematically evaluates both choices at every hour and guarantees the optimal total. Time complexity is O(n) because each index is processed once, and space complexity is O(n) for the DP arrays.

Approach 2: Greedy with Pruning (O(n) time, O(1) space)

A more space‑efficient variation observes that each state depends only on the previous one or two hours. Instead of storing full DP arrays, keep rolling variables representing the best totals for the last two positions for each drink. At each step, compute the gain for continuing the same drink or switching after the cooldown, then keep only the maximum candidate. Greedy pruning discards dominated states where continuing or switching would always produce a smaller total than another tracked option. Because only constant state is maintained, the algorithm runs in O(n) time with O(1) extra space. This version is preferred when memory usage matters or when implementing a concise interview solution.

Recommended for interviews: The dynamic programming formulation is the expected explanation because it clearly models the cooldown constraint and state transitions. Writing the full DP first demonstrates solid reasoning about state definition and recurrence. After that, optimizing to rolling variables (the greedy‑pruned version) shows deeper understanding of DP space reduction.

Approach 1: Dynamic Programming Solution

This approach involves using dynamic programming to track the maximum energy boost at each hour when choosing between continuing with the current drink or switching to the other, accounting for the necessary hour idle when switching.

Python

def max_energy(A, B):
    n = len(A)
    dpA = [0] * n
    dpB = [0] * n
    dpA[0], dpB[0] = A[0], B[0]
    for i in range(1, n):
        dpA[i] = A[i] + max(dpA[i-1], dpB[i-2] if i > 1 else 0)
        dpB[i] = B[i] + max(dpB[i-1], dpA[i-2] if i > 1 else 0)
    return max(dpA[-1], dpB[-1])

energyDrinkA = [4, 1, 1]
energyDrinkB = [1, 1, 3]
print(max_energy(energyDrinkA, energyDrinkB))

Java

import java.util.Arrays;

public class Main {
    public static int maxEnergy(int[] A, int[] B) {
        int n = A.length;
        int[] dpA = new int[n];
        int[] dpB = new int[n];
        dpA[0] = A[0];
        dpB[0] = B[0];
        for (int i = 1; i < n; ++i) {
            dpA[i] = A[i] + Math.max(dpA[i-1], (i > 1 ? dpB[i-2] : 0));
            dpB[i] = B[i] + Math.max(dpB[i-1], (i > 1 ? dpA[i-2] : 0));
        }
        return Math.max(dpA[n-1], dpB[n-1]);
    }

    public static void main(String[] args) {
        int[] A = {4, 1, 1};
        int[] B = {1, 1, 3};
        System.out.println(maxEnergy(A, B));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>

int maxEnergy(std::vector<int>& A, std::vector<int>& B) {
    int n = A.size();
    std::vector<int> dpA(n), dpB(n);
    dpA[0] = A[0];
    dpB[0] = B[0];
    for (int i = 1; i < n; ++i) {
        dpA[i] = A[i] + std::max(dpA[i-1], (i > 1 ? dpB[i-2] : 0));
        dpB[i] = B[i] + std::max(dpB[i-1], (i > 1 ? dpA[i-2] : 0));
    }
    return std::max(dpA[n-1], dpB[n-1]);
}

int main() {
    std::vector<int> A = {4, 1, 1};
    std::vector<int> B = {1, 1, 3};
    std::cout << maxEnergy(A, B) << std::endl;
    return 0;
}

JavaScript

function maxEnergy(A, B) {
    const n = A.length;
    const dpA = Array(n).fill(0);
    const dpB = Array(n).fill(0);
    dpA[0] = A[0];
    dpB[0] = B[0];
    for (let i = 1; i < n; i++) {
        dpA[i] = A[i] + Math.max(dpA[i-1], i > 1 ? dpB[i-2] : 0);
        dpB[i] = B[i] + Math.max(dpB[i-1], i > 1 ? dpA[i-2] : 0);
    }
    return Math.max(dpA[n-1], dpB[n-1]);
}

const energyDrinkA = [4, 1, 1];
const energyDrinkB = [1, 1, 3];
console.log(maxEnergy(energyDrinkA, energyDrinkB));

#include <stdio.h>

int maxEnergy(int* A, int* B, int n) {
    int dpA[n], dpB[n];
    dpA[0] = A[0];
    dpB[0] = B[0];
    for (int i = 1; i < n; ++i) {
        dpA[i] = A[i] + (i > 1 ? (dpA[i-1] > dpB[i-1] ? dpA[i-1] : dpB[i-2]) : dpB[i-1]);
        dpB[i] = B[i] + (i > 1 ? (dpB[i-1] > dpA[i-1] ? dpB[i-1] : dpA[i-2]) : dpA[i-1]);
    }
    return dpA[n-1] > dpB[n-1] ? dpA[n-1] : dpB[n-1];
}

int main() {
    int A[] = {4, 1, 1};
    int B[] = {1, 1, 3};
    int n = 3;
    printf("%d\n", maxEnergy(A, B, n));
    return 0;
}

using System;

class Program {
    static int MaxEnergy(int[] A, int[] B) {
        int n = A.Length;
        int[] dpA = new int[n];
        int[] dpB = new int[n];
        dpA[0] = A[0];
        dpB[0] = B[0];
        for (int i = 1; i < n; ++i) {
            dpA[i] = A[i] + Math.Max(dpA[i-1], i > 1 ? dpB[i-2] : 0);
            dpB[i] = B[i] + Math.Max(dpB[i-1], i > 1 ? dpA[i-2] : 0);
        }
        return Math.Max(dpA[n-1], dpB[n-1]);
    }

    static void Main() {
        int[] A = {4, 1, 1};
        int[] B = {1, 1, 3};
        Console.WriteLine(MaxEnergy(A, B));
    }
}

The Python solution creates two lists, dpA and dpB, which store the maximum possible energy boost up to each hour using drink A and B. The logic is identical to the C/C++/Java versions but uses Python's list and range functionalities for iteration control.

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor

Approach 2: Greedy Approach with Pruning

This approach uses a greedy method to consider maximum energy at each point and prune the possibility of switching drinks smartly to avoid unnecessary calculations. It initiates from collecting max energy without switching and checks switch influence cautiously without calculating every possibility.

Python

def max_energy_greedy(A, B):
    max_energy_a = max_energy_b = max_a = max_b = 0
    for i in range(len(A)):
        max_a += A[i]
        max_b += B[i]
        if i > 0:
            switch_energy_a = max_energy_b + A[i]
            switch_energy_b = max_energy_a + B[i]
            max_a = max(max_a, switch_energy_a)
            max_b = max(max_b, switch_energy_b)
        max_energy_a = max(max_energy_a, max_a)
        max_energy_b = max(max_energy_b, max_b)
    return max(max_energy_a, max_energy_b)

energyDrinkA = [4, 1, 1]
energyDrinkB = [1, 1, 3]
print(max_energy_greedy(energyDrinkA, energyDrinkB))

Java

public class Main {
    public static int maxEnergyGreedy(int[] A, int[] B) {
        int maxEnergyA = 0, maxEnergyB = 0;
        int maxA = 0, maxB = 0;
        for (int i = 0; i < A.length; ++i) {
            maxA += A[i];
            maxB += B[i];
            if (i > 0) {
                int switchEnergyA = maxEnergyB + A[i];
                int switchEnergyB = maxEnergyA + B[i];
                maxA = Math.max(maxA, switchEnergyA);
                maxB = Math.max(maxB, switchEnergyB);
            }
            maxEnergyA = Math.max(maxEnergyA, maxA);
            maxEnergyB = Math.max(maxEnergyB, maxB);
        }
        return Math.max(maxEnergyA, maxEnergyB);
    }

    public static void main(String[] args) {
        int[] A = {4, 1, 1};
        int[] B = {1, 1, 3};
        System.out.println(maxEnergyGreedy(A, B));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>

int maxEnergyGreedy(std::vector<int>& A, std::vector<int>& B) {
    int maxEnergyA = 0, maxEnergyB = 0;
    int maxA = 0, maxB = 0;
    for (size_t i = 0; i < A.size(); ++i) {
        maxA += A[i];
        maxB += B[i];
        if (i > 0) {
            int switchEnergyA = maxEnergyB + A[i];
            int switchEnergyB = maxEnergyA + B[i];
            maxA = std::max(maxA, switchEnergyA);
            maxB = std::max(maxB, switchEnergyB);
        }
        maxEnergyA = std::max(maxEnergyA, maxA);
        maxEnergyB = std::max(maxEnergyB, maxB);
    }
    return std::max(maxEnergyA, maxEnergyB);
}

int main() {
    std::vector<int> A = {4, 1, 1};
    std::vector<int> B = {1, 1, 3};
    std::cout << maxEnergyGreedy(A, B) << std::endl;
    return 0;
}

JavaScript

function maxEnergyGreedy(A, B) {
    let maxEnergyA = 0, maxEnergyB = 0;
    let maxA = 0, maxB = 0;
    for (let i = 0; i < A.length; i++) {
        maxA += A[i];
        maxB += B[i];
        if (i > 0) {
            let switchEnergyA = maxEnergyB + A[i];
            let switchEnergyB = maxEnergyA + B[i];
            maxA = Math.max(maxA, switchEnergyA);
            maxB = Math.max(maxB, switchEnergyB);
        }
        maxEnergyA = Math.max(maxEnergyA, maxA);
        maxEnergyB = Math.max(maxEnergyB, maxB);
    }
    return Math.max(maxEnergyA, maxEnergyB);
}

const energyDrinkA = [4, 1, 1];
const energyDrinkB = [1, 1, 3];
console.log(maxEnergyGreedy(energyDrinkA, energyDrinkB));

#include <stdio.h>

int maxEnergyGreedy(int* A, int* B, int n) {
    int maxEnergyA = 0, maxEnergyB = 0;
    int maxA = 0, maxB = 0;
    for (int i = 0; i < n; ++i) {
        maxA += A[i];
        maxB += B[i];
        if (i > 0) {
            int switchEnergyA = maxEnergyB + A[i];
            int switchEnergyB = maxEnergyA + B[i];
            if (switchEnergyA > maxA) maxA = switchEnergyA;
            if (switchEnergyB > maxB) maxB = switchEnergyB;
        }
        if (maxA > maxEnergyA) maxEnergyA = maxA;
        if (maxB > maxEnergyB) maxEnergyB = maxB;
    }
    return maxEnergyA > maxEnergyB ? maxEnergyA : maxEnergyB;
}

int main() {
    int A[] = {4, 1, 1};
    int B[] = {1, 1, 3};
    int n = 3;
    printf("%d\n", maxEnergyGreedy(A, B, n));
    return 0;
}

using System;

class Program {
    static int MaxEnergyGreedy(int[] A, int[] B) {
        int maxEnergyA = 0, maxEnergyB = 0;
        int maxA = 0, maxB = 0;
        for (int i = 0; i < A.Length; ++i) {
            maxA += A[i];
            maxB += B[i];
            if (i > 0) {
                int switchEnergyA = maxEnergyB + A[i];
                int switchEnergyB = maxEnergyA + B[i];
                maxA = Math.Max(maxA, switchEnergyA);
                maxB = Math.Max(maxB, switchEnergyB);
            }
            maxEnergyA = Math.Max(maxEnergyA, maxA);
            maxEnergyB = Math.Max(maxEnergyB, maxB);
        }
        return Math.Max(maxEnergyA, maxEnergyB);
    }

    static void Main() {
        int[] A = {4, 1, 1};
        int[] B = {1, 1, 3};
        Console.WriteLine(MaxEnergyGreedy(A, B));
    }
}

In Python, the greedy solution advances hour by hour evaluating cumulative max energy without switching normally, while investing decisions on possible beneficial switch scenarios at each point.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][0] to represent the maximum boost energy obtained by choosing energy drink A at the i-th hour, and f[i][1] to represent the maximum boost energy obtained by choosing energy drink B at the i-th hour. Initially, f[0][0] = energyDrinkA[0], f[0][1] = energyDrinkB[0]. The answer is max(f[n - 1][0], f[n - 1][1]).

For i > 0, we have the following state transition equations:

$\begin{aligned} 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]) \end{aligned}

Finally, return max(f[n - 1][0], f[n - 1][1]).

The time complexity is O(n), and the space complexity is O(n). Here, n$ is the length of the array.

TypeScript

function maxEnergyBoost(energyDrinkA: number[], energyDrinkB: number[]): number {
    const n = energyDrinkA.length;
    const f: number[][] = Array.from({ length: n }, () => [0, 0]);
    f[0][0] = energyDrinkA[0];
    f[0][1] = energyDrinkB[0];
    for (let 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]!);
}

func maxEnergyBoost(energyDrinkA []int, energyDrinkB []int) int64 {
	n := len(energyDrinkA)
	f := make([][2]int64, n)
	f[0][0] = int64(energyDrinkA[0])
	f[0][1] = int64(energyDrinkB[0])
	for i := 1; i < n; i++ {
		f[i][0] = max(f[i-1][0]+int64(energyDrinkA[i]), f[i-1][1])
		f[i][1] = max(f[i-1][1]+int64(energyDrinkB[i]), f[i-1][0])
	}
	return max(f[n-1][0], f[n-1][1])
}

Try this approach in the editor

Approach 4: Dynamic Programming (Space Optimization)

We notice that the state f[i] is only related to f[i - 1] and not to f[i - 2]. Therefore, we can use only two variables f and g to maintain the state, thus optimizing the space complexity to O(1).

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function maxEnergyBoost(energyDrinkA: number[], energyDrinkB: number[]): number {
    const n = energyDrinkA.length;
    let [f, g] = [energyDrinkA[0], energyDrinkB[0]];
    for (let i = 1; i < n; ++i) {
        [f, g] = [Math.max(f + energyDrinkA[i], g), Math.max(g + energyDrinkB[i], f)];
    }
    return Math.max(f, g);
}

func maxEnergyBoost(energyDrinkA []int, energyDrinkB []int) int64 {
	n := len(energyDrinkA)
	f, g := energyDrinkA[0], energyDrinkB[0]
	for i := 1; i < n; i++ {
		f, g = max(f+energyDrinkA[i], g), max(g+energyDrinkB[i], f)
	}
	return int64(max(f, g))
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Solution	Time Complexity: O(n) Space Complexity: O(n)
Greedy Approach with Pruning	Time Complexity: O(n) Space Complexity: O(1)
Dynamic Programming	–
Dynamic Programming (Space Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming	O(n)	O(n)	Best for explaining the recurrence and cooldown transition clearly in interviews
Greedy with Pruning (Rolling DP)	O(n)	O(1)	When optimizing memory or implementing a concise production solution

Frequently asked questions

Is Maximum Energy Boost From Two Drinks easy or hard?

Maximum Energy Boost From Two Drinks is typically classified as a Medium problem. The difficulty comes from recognizing the cooldown constraint and modeling it with the correct DP transition using the previous two indices.

Maximum Energy Boost From Two Drinks Python/Java solution

Most implementations follow the same DP recurrence regardless of language. Maintain two arrays or variables for drink A and drink B totals, update them in a loop, and return the maximum at the final hour. This approach works cleanly in Python, Java, C++, C#, and JavaScript.

How to solve Maximum Energy Boost From Two Drinks in O(n)?

Maintain two running values representing the best energy totals if the current hour uses drink A or drink B. For each hour, either continue the same drink (add the current energy) or switch from the other drink while respecting the one‑hour cooldown. Update the states sequentially in a single pass through the arrays.

What is the best approach for Maximum Energy Boost From Two Drinks?

Dynamic programming is the most reliable approach. Track two states: the maximum energy when ending the current hour with drink A or drink B. Each state either continues the same drink or switches after a one‑hour cooldown. This produces an optimal O(n) time solution.

Is Maximum Energy Boost From Two Drinks asked at Google/Amazon/Meta?

Problems combining arrays with dynamic programming transitions appear frequently in interviews at companies like Google, Amazon, and Meta. Variants with cooldown constraints are especially common because they test state modeling and DP optimization skills.

What data structure is used in Maximum Energy Boost From Two Drinks?

The main structure is a dynamic programming state table or rolling variables. The input itself is handled as arrays, and the algorithm updates two DP states per index to represent the best energy ending with each drink.

What is the time complexity of Maximum Energy Boost From Two Drinks?

The optimal solution runs in O(n) time because each hour is processed once while updating two DP states. Space complexity is O(n) with full DP arrays or O(1) when optimized with rolling variables.

Maximum Energy Boost From Two Drinks solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Solution

Approach 2: Greedy Approach with Pruning

Approach 3: Dynamic Programming

Approach 4: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Energy Boost From Two Drinks solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Solution

Approach 2: Greedy Approach with Pruning

Approach 3: Dynamic Programming

Approach 4: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems