金苹果岛算法题解：最大化代码能力的最优策略

金苹果岛算法题解：最大化代码能力的最优策略

题目描述:

你是一位代码勇者，来到了拥有红苹果和金苹果的'金苹果岛'。吃下红苹果会提升你的代码能力（提升值可能为负），吃下金苹果则会使你的代码能力翻倍。

你需要制定一个策略，在吃掉所有苹果的情况下，最大化你的最终代码能力。

输入:

• 红苹果数量 n 和金苹果数量 m。* n 个整数，表示每个红苹果对代码能力的提升值。

输出:

• 最终代码能力的最大值。

解题思路:

由于金苹果的效果是翻倍，为了最大化最终能力，我们应该在代码能力'尽可能大'的时候吃金苹果。

1. 遍历红苹果: 计算吃完每个红苹果后的代码能力。2. 维护最大能力: 在遍历过程中，记录出现的最大代码能力。3. 最终翻倍: 遍历结束后，将记录的最大能力乘以 2 的 m 次方（金苹果的效果）。

**代码实现 (Python):**pythonn, m = map(int, input().split())apples = list(map(int, input().split()))

max_ability = 1cur_ability = 1for a in apples: cur_ability += a max_ability = max(max_ability, cur_ability) if cur_ability <= 0: cur_ability = 1

print(max_ability * 2**m)

代码解释:

• max_ability: 记录出现的最大代码能力。* cur_ability: 当前代码能力。* 遍历红苹果，更新 cur_ability，并用 max_ability 记录最大值。* 如果 cur_ability 小于等于 0，则重置为 1，因为从 1 开始增长总比继续负数状态好。* 最后将 max_ability 乘以 2**m，表示使用所有金苹果翻倍后的结果。

时间复杂度: O(n)

空间复杂度: O(1)