3259.超级饮料的最大强化能量

【LetMeFly】3259.超级饮料的最大强化能量：动态规划（O(1)空间）

力扣题目链接：https://leetcode.cn/problems/maximum-energy-boost-from-two-drinks/

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

 

示例 1：

输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]

输出：5

解释：

要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。

示例 2：

输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]

输出：7

解释：

• 第一个小时饮用能量饮料 A。
• 切换到能量饮料 B ，在第二个小时无法获得强化能量。
• 第三个小时饮用能量饮料 B ，并获得强化能量。

 

提示：

• n == energyDrinkA.length == energyDrinkB.length
• 3 <= n <= 105
• 1 <= energyDrinkA[i], energyDrinkB[i] <= 105

解题方法：动态规划（原地滚动）

使用4个变量：

• day0a代表第0天使用A能量饮料时的最大总能量
• day0b代表第0天使用B能量饮料时的最大总能量
• day1a代表第1天使用A能量饮料时的最大总能量
• day1b代表第1天使用B能量饮料时的最大总能量

那么对于第“2”天：

• 选择饮料A的话：可以第1天就是饮料A（day1a），也可以第1天不喝然后第0天是饮料B（day0b）。最终到这天为止的总能量为$\max(day1a, day0b) + energyB[i]$
• 选择饮料B的话：同理，最大总能量为$\max(day0a, day1b) + energyB[i]$

变量过程中更新维护这4个变量，最终返回$\max(day1a, day1b)$即为答案。（因为$day1a$一定大于$day0a$，$day1b$一定大于$day0b$）

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        ll day0a = 0, day0b = 0, day1a = energyDrinkA[0], day1b = energyDrinkB[0];
        for (int i = 1; i < energyDrinkA.size(); i++) {
            ll day2a = max(day1a, day0b) + energyDrinkA[i];
            ll day2b = max(day0a, day1b) + energyDrinkB[i];
            day0a = day1a, day0b = day1b, day1a = day2a, day1b = day2b;
        }
        return max(day1a, day1b);
    }
};

时空复杂度超越百分比：AC,100.00%,94.62%。

Python

from typing import List

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        day0a, day0b, day1a, day1b = 0, 0, energyDrinkA[0], energyDrinkB[0]
        for i in range(1, len(energyDrinkA)):
            day0a, day0b, day1a, day1b = day1a, day1b, max(day1a, day0b) + energyDrinkA[i], max(day0a, day1b) + energyDrinkB[i]
        return max(day1a, day1b)

Java

class Solution {
    public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
        long day0a = 0, day0b = 0, day1a = energyDrinkA[0], day1b = energyDrinkB[0];
        for (int i = 1; i < energyDrinkA.length; i++) {
            long day2a = Math.max(day1a, day0b) + energyDrinkA[i], day2b = Math.max(day0a, day1b) + energyDrinkB[i];
            day0a = day1a;
            day0b = day1b;
            day1a = day2a;
            day1b = day2b;
        }
        return Math.max(day1a, day1b);
    }
}

Go

package main

func max(a int64, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func maxEnergyBoost(energyDrinkA []int, energyDrinkB []int) int64 {
    var day0a, day0b, day1a, day1b int64 = 0, 0, int64(energyDrinkA[0]), int64(energyDrinkB[0])
    for i := 1; i < len(energyDrinkA); i++ {
        day0a, day0b, day1a, day1b = day1a, day1b, max(day1a, day0b) + int64(energyDrinkA[i]), max(day0a, day1b) + int64(energyDrinkB[i])
    }
    return max(day1a, day1b)
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143429899