第25章 面试题：买卖股票的最佳时机

在算法面试中，股票买卖问题是一类经典且常考的动态规划或贪心算法问题。这类问题不仅考验了应聘者对算法的理解深度，还检验了其逻辑思维能力和问题解决能力。本章将深入探讨“买卖股票的最佳时机”这一问题，通过详细分析题目要求、解法思路、代码实现及优化策略，帮助读者在面试中从容应对此类难题。

一、题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

二、问题分析

这个问题看似简单，实则蕴含了多种解法思路。首先，我们需要明确题目中的几个关键点：

1. 多次交易：允许在同一天内多次买卖，但每次买卖之间必须有一个非交易日作为间隔（即不能同时持有两支股票）。
2. 最大化利润：目标是使通过买卖股票获得的利润最大化。

基于上述分析，我们可以采用以下几种策略来解决这个问题：

• 贪心算法：由于允许在同一天内多次买卖，我们可以简单地遍历价格数组，累加所有相邻两天之间的正价差（即如果第 i 天的价格高于第 i-1 天，则计算这两天的价差作为一次交易的利润）。这种方法适用于允许多次交易且没有交易费用的情况。
• 动态规划：虽然本题通过贪心算法即可解决，但了解动态规划的思路对于处理更复杂的股票买卖问题（如只能进行一次交易、两次交易等）至关重要。

三、解法一：贪心算法

贪心算法的核心思想是，只要今天的价格比昨天高，就选择卖出，并在今天买入（或理解为在昨天买入，今天卖出），以获取这段上涨的利润。由于可以多次交易，我们只需关注每一天与前一天的价差即可。

代码实现（Python）：

def maxProfit(prices):
    if not prices:
        return 0
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            max_profit += prices[i] - prices[i-1]
    return max_profit

四、解法二：动态规划（虽非必要，但作为扩展）

虽然本题不需要动态规划，但了解动态规划在股票买卖问题中的应用对于解决更复杂的版本（如只能交易一次、两次等）至关重要。

假设 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润。则有状态转移方程：

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：表示第 i 天不持股，可以由前一天不持股直接得到，或者前一天持股今天卖出。
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])：表示第 i 天持股，可以由前一天持股直接得到，或者前一天不持股今天买入。

但注意，由于本题允许无限次交易，且没有交易费，动态规划的状态转移可以简化为贪心策略。

五、扩展问题

• 只能交易一次：此时需要使用动态规划，且状态转移方程如上所述，但只需考虑 dp[i][0]，因为最终目标是最大化不持股时的利润。
• 只能交易两次：在只能交易一次的基础上，引入一个新的维度或状态来记录已完成的交易次数。
• 含交易费用：在每次交易时，扣除固定的交易费用，这会影响决策过程，通常需要使用更复杂的动态规划策略。

六、总结

“买卖股票的最佳时机”问题是一类经典的算法面试题，通过贪心算法可以高效地解决允许多次交易且没有交易费用的情况。同时，了解动态规划在股票买卖问题中的应用，有助于解决更复杂的问题变体。在面试中，除了正确实现算法外，清晰地阐述解题思路、分析时间复杂度和空间复杂度也是非常重要的。希望本章内容能帮助读者在面试中脱颖而出，成功通关算法面试。