3259. Maximum Energy Boost From Two Drinks

Description

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⁵

Solutions

Solution 1: Dynamic Programming

Thinking

Each hour we drink A or B, and switching costs a clean hour. \(n\le 10^5\) forbids enumerating switch points. The optimum at hour \(i\) depends only on which drink was last chosen.

\(f[i][0]\) / \(f[i][1]\) are the best scores ending on A / B: continue the same drink and add today's value, or come from the other drink as a clean gap without adding. The answer is the larger last-row entry.

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] = \textit{energyDrinkA}[0]\), \(f[0][1] = \textit{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] + \textit{energyDrinkA}[i], f[i - 1][1]) \\ f[i][1] & = \max(f[i - 1][1] + \textit{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.

Python3JavaC++GoTypeScript

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        n = len(energyDrinkA)
        f = [[0] * 2 for _ in range(n)]
        f[0][0] = energyDrinkA[0]
        f[0][1] = energyDrinkB[0]
        for i in range(1, n):
            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])
        return max(f[n - 1])

class Solution {
    public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
        int n = energyDrinkA.length;
        long[][] f = new long[n][2];
        f[0][0] = energyDrinkA[0];
        f[0][1] = energyDrinkB[0];
        for (int 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][0], f[n - 1][1]);
    }
}

class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        vector<vector<long long>> f(n, vector<long long>(2));
        f[0][0] = energyDrinkA[0];
        f[0][1] = energyDrinkB[0];
        for (int i = 1; i < n; ++i) {
            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]);
        }
        return max(f[n - 1][0], f[n - 1][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])
}

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]!);
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

Solution 1 reads only \(f[i-1]\), so the table collapses to two variables. Rolling \(f,g\) store the best scores for A and B; space becomes \(O(1)\) at the same time.

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)\).

Python3JavaC++GoTypeScript

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        f, g = energyDrinkA[0], energyDrinkB[0]
        for a, b in zip(energyDrinkA[1:], energyDrinkB[1:]):
            f, g = max(f + a, g), max(g + b, f)
        return max(f, g)

class Solution {
    public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
        int n = energyDrinkA.length;
        long f = energyDrinkA[0], g = energyDrinkB[0];
        for (int i = 1; i < n; ++i) {
            long ff = Math.max(f + energyDrinkA[i], g);
            g = Math.max(g + energyDrinkB[i], f);
            f = ff;
        }
        return Math.max(f, g);
    }
}

class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        long long f = energyDrinkA[0], g = energyDrinkB[0];
        for (int i = 1; i < n; ++i) {
            long long ff = max(f + energyDrinkA[i], g);
            g = max(g + energyDrinkB[i], f);
            f = ff;
        }
        return 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))
}

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);
}

3259. Maximum Energy Boost From Two Drinks

Description

Solutions

Solution 1: Dynamic Programming

Solution 2: Dynamic Programming (Space Optimization)

Comments