Maximum Energy Boost From Two Drinks

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.

Examples

Example 1

1
2
3
4
5
6
7
8



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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12



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

Solution

Method 1 – Dynamic Programming

Intuition

We can use dynamic programming to track the maximum energy boost if we end the current hour with drink A or drink B. If we switch, we must skip an hour (no energy boost that hour).

Approach

Let dpA[i] be the max energy boost up to hour i if we drink A at hour i.
Let dpB[i] be the max energy boost up to hour i if we drink B at hour i.
For hour 0, dpA[0] = energyDrinkA[0], dpB[0] = energyDrinkB[0].
For each hour i > 0:
- dpA[i] = max(dpA[i-1] + energyDrinkA[i], dpB[i-2] + energyDrinkA[i] if i > 1 else 0)
- dpB[i] = max(dpB[i-1] + energyDrinkB[i], dpA[i-2] + energyDrinkB[i] if i > 1 else 0)
The answer is the maximum of the last values in dpA and dpB.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    int maxEnergyBoost(vector<int>& a, vector<int>& b) {
        int n = a.size();
        vector<int> dpA(n), dpB(n);
        dpA[0] = a[0];
        dpB[0] = b[0];
        for (int i = 1; i < n; ++i) {
            dpA[i] = max(dpA[i-1] + a[i], (i > 1 ? dpB[i-2] : 0) + a[i]);
            dpB[i] = max(dpB[i-1] + b[i], (i > 1 ? dpA[i-2] : 0) + b[i]);
        }
        return max(dpA[n-1], dpB[n-1]);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func maxEnergyBoost(a, b []int) int {
    n := len(a)
    dpA := make([]int, n)
    dpB := make([]int, n)
    dpA[0], dpB[0] = a[0], b[0]
    for i := 1; i < n; i++ {
        dpA[i] = max(dpA[i-1]+a[i], (func() int { if i > 1 { return dpB[i-2] } else { return 0 } })()+a[i])
        dpB[i] = max(dpB[i-1]+b[i], (func() int { if i > 1 { return dpA[i-2] } else { return 0 } })()+b[i])
    }
    if dpA[n-1] > dpB[n-1] {
        return dpA[n-1]
    }
    return dpB[n-1]
}
func max(a, b int) int { if a > b { return a } else { return b } }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    public int maxEnergyBoost(int[] a, int[] b) {
        int n = a.length;
        int[] dpA = new int[n], dpB = new int[n];
        dpA[0] = a[0];
        dpB[0] = b[0];
        for (int i = 1; i < n; i++) {
            dpA[i] = Math.max(dpA[i-1] + a[i], (i > 1 ? dpB[i-2] : 0) + a[i]);
            dpB[i] = Math.max(dpB[i-1] + b[i], (i > 1 ? dpA[i-2] : 0) + b[i]);
        }
        return Math.max(dpA[n-1], dpB[n-1]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    fun maxEnergyBoost(a: IntArray, b: IntArray): Int {
        val n = a.size
        val dpA = IntArray(n)
        val dpB = IntArray(n)
        dpA[0] = a[0]
        dpB[0] = b[0]
        for (i in 1 until n) {
            dpA[i] = maxOf(dpA[i-1]+a[i], (if (i > 1) dpB[i-2] else 0) + a[i])
            dpB[i] = maxOf(dpB[i-1]+b[i], (if (i > 1) dpA[i-2] else 0) + b[i])
        }
        return maxOf(dpA[n-1], dpB[n-1])
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def maxEnergyBoost(self, a: list[int], b: list[int]) -> int:
        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] = max(dpA[i-1]+a[i], (dpB[i-2] if i > 1 else 0) + a[i])
            dpB[i] = max(dpB[i-1]+b[i], (dpA[i-2] if i > 1 else 0) + b[i])
        return max(dpA[-1], dpB[-1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


impl Solution {
    pub fn max_energy_boost(a: Vec<i32>, b: Vec<i32>) -> i32 {
        let n = a.len();
        let mut dp_a = vec![0; n];
        let mut dp_b = vec![0; n];
        dp_a[0] = a[0];
        dp_b[0] = b[0];
        for i in 1..n {
            dp_a[i] = dp_a[i-1] + a[i];
            if i > 1 {
                dp_a[i] = dp_a[i].max(dp_b[i-2] + a[i]);
            }
            dp_b[i] = dp_b[i-1] + b[i];
            if i > 1 {
                dp_b[i] = dp_b[i].max(dp_a[i-2] + b[i]);
            }
        }
        dp_a[n-1].max(dp_b[n-1])
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    maxEnergyBoost(a: number[], b: number[]): number {
        const n = a.length;
        const dpA = new Array(n).fill(0), dpB = new Array(n).fill(0);
        dpA[0] = a[0];
        dpB[0] = b[0];
        for (let i = 1; i < n; i++) {
            dpA[i] = Math.max(dpA[i-1]+a[i], (i > 1 ? dpB[i-2] : 0) + a[i]);
            dpB[i] = Math.max(dpB[i-1]+b[i], (i > 1 ? dpA[i-2] : 0) + b[i]);
        }
        return Math.max(dpA[n-1], dpB[n-1]);
    }
}

Complexity

⏰ Time complexity: O(n), where n is the number of hours, as we process each hour once.
🧺 Space complexity: O(n), for the DP arrays.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#