Maximum Energy Boost From Two Drinks

Medium
1495.

Maximum Energy Boost From Two Drinks

Maximum Energy Boost From Two Drinks is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

Two arrays of length n, energyDrinkA and energyDrinkB, give the energy boost each drink provides in each of the next n hours.

Every hour you drink one of the two, starting with either. To switch from one drink to the other you must spend one hour cleansing your system, gaining nothing that hour.

Return the maximum total energy boost over the n hours.

CodeKairo bound: boosts are at most 10^4 (LeetCode allows 10^5) so that the total fits in a 32-bit integer.

Example 1

Input
energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
Output
5
Explanation
Drink only A (1 + 3 + 1) or only B (3 + 1 + 1).

Example 2

Input
energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
Output
7
Explanation
A in hour 0, cleanse in hour 1, B in hour 2.

Example 3

Input
energyDrinkA = [2,2,9,1], energyDrinkB = [5,5,1,1]
Output
15
Explanation
B, cleanse, A, A: 5 + 9 + 1.

Constraints

  • n == energyDrinkA.length == energyDrinkB.length
  • 3 <= n <= 10^5
  • 1 <= energyDrinkA[i], energyDrinkB[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} energyDrinkA
 * @param {number[]} energyDrinkB
 * @return {number}
 */
var maxEnergyBoost = function(energyDrinkA, energyDrinkB) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Energy Boost From Two Drinks — Problem & Solution

Maximum Energy Boost From Two Drinks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Energy Boost From Two Drinks is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two arrays of length n, energyDrinkA and energyDrinkB, give the energy boost each drink provides in each of the next n hours.

Every hour you drink one of the two, starting with either. To switch from one drink to the other you must spend one hour cleansing your system, gaining nothing that hour.

Return the maximum total energy boost over the n hours.

CodeKairo bound: boosts are at most 10^4 (LeetCode allows 10^5) so that the total fits in a 32-bit integer.

Example 1

Input: energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
Output: 5
Explanation: Drink only A (1 + 3 + 1) or only B (3 + 1 + 1).

Example 2

Input: energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
Output: 7
Explanation: A in hour 0, cleanse in hour 1, B in hour 2.

Example 3

Input: energyDrinkA = [2,2,9,1], energyDrinkB = [5,5,1,1]
Output: 15
Explanation: B, cleanse, A, A: 5 + 9 + 1.

Constraints

  • n == energyDrinkA.length == energyDrinkB.length
  • 3 <= n <= 10^5
  • 1 <= energyDrinkA[i], energyDrinkB[i] <= 10^4

Hints for Maximum Energy Boost From Two Drinks

  1. Hint 1

    Track the best total that ends with each drink at hour i.

  2. Hint 2

    To drink A at hour i, the previous hour was either A, or a cleansing hour after B at hour i - 2.

  3. Hint 3

    a[i] = max(a[i-1], b[i-2]) + A[i] and symmetrically for b[i].

How to solve Maximum Energy Boost From Two Drinks

Two-state DP. A switch costs exactly one hour, so the hour before an A-drink is either another A-drink or the cleanse that followed a B-drink two hours earlier.

Approach

  1. a[0] = A[0], b[0] = B[0]; treat a[-1] = b[-1] = 0.
  2. For i >= 1: a[i] = max(a[i-1], b[i-2]) + A[i], b[i] = max(b[i-1], a[i-2]) + B[i].
  3. Return max(a[n-1], b[n-1]); only the last two values of each are ever needed.

Why it works

In an optimal plan the hour before drinking A at hour i either holds an A-drink (continue) or is a cleanse; a cleanse is only ever worth taking to switch, so the hour before it holds a B-drink. Both predecessors are optimal sub-plans, so the recurrence is exact (an unnecessary idle hour never helps because every boost is positive).

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Switching does not cost the next drink — it costs one whole hour of boost.
  • You may start with either drink; do not force a start with A.
  • With LeetCode's original bounds the total needs 64 bits; the tightened bound keeps it in 32.

Reference solution

Python

from typing import List

def maxEnergyBoost(energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
    a, b = energyDrinkA, energyDrinkB
    pa = pb = 0
    ca, cb = a[0], b[0]
    for i in range(1, len(a)):
        na = max(ca, pb) + a[i]
        nb = max(cb, pa) + b[i]
        pa, pb = ca, cb
        ca, cb = na, nb
    return max(ca, cb)

Java

public static int maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
    int pa = 0, pb = 0;
    int ca = energyDrinkA[0], cb = energyDrinkB[0];
    for (int i = 1; i < energyDrinkA.length; i++) {
        int na = Math.max(ca, pb) + energyDrinkA[i];
        int nb = Math.max(cb, pa) + energyDrinkB[i];
        pa = ca; pb = cb;
        ca = na; cb = nb;
    }
    return Math.max(ca, cb);
}

C++

int maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
    int pa = 0, pb = 0;
    int ca = energyDrinkA[0], cb = energyDrinkB[0];
    for (size_t i = 1; i < energyDrinkA.size(); i++) {
        int na = max(ca, pb) + energyDrinkA[i];
        int nb = max(cb, pa) + energyDrinkB[i];
        pa = ca; pb = cb;
        ca = na; cb = nb;
    }
    return max(ca, cb);
}

JavaScript

var maxEnergyBoost = function(energyDrinkA, energyDrinkB) {
    var pa = 0, pb = 0;
    var ca = energyDrinkA[0], cb = energyDrinkB[0];
    for (var i = 1; i < energyDrinkA.length; i++) {
        var na = Math.max(ca, pb) + energyDrinkA[i];
        var nb = Math.max(cb, pa) + energyDrinkB[i];
        pa = ca; pb = cb;
        ca = na; cb = nb;
    }
    return Math.max(ca, cb);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming