有趣的Leecode - 买卖股票的最佳时机

1. 买卖股票的最佳时机问题简介

买卖股票的最佳时机(LeetCode 121)是一个经典的动态规划问题。给定一个数组prices，第i个元素表示股票在第i天的价格。可以进行多次交易，但是必须先卖出手中的股票才能再次购买股票，而且只能拥有一支股票。

问题要求找出可以获得的最大收益。

2. 解决思路

2.1. 暴力法

暴力法是一种简单但低效的解法。对于每个时间点i，都计算卖出的最大利润并更新最大利润值。

算法步骤如下：

max_profit = 0

for i in range(len(prices)):
    for j in range(i+1, len(prices)):
        profit = prices[j] - prices[i]
        if profit > max_profit:
            max_profit = profit
return max_profit

时间复杂度：O(n^2)

在实际代码中的优化：通过遍历一次数组，记录到当前天为止的最低价格min_price和最大利润max_profit。若当前价格小于最低价格，则更新最低价格，否则计算当前价格与最低价格的利润，并更新最大利润。

min_price = float('inf')

max_profit = 0
for price in prices:
    if price < min_price:
        min_price = price
    elif price - min_price > max_profit:
        max_profit = price - min_price
return max_profit

时间复杂度：O(n)

2.2. 动态规划

动态规划是解决本问题的最优解法。定义状态dp[i]表示到第i天为止的最大利润。如果第i天卖出股票，则前i-1天的最大利润为dp[i-1]，第i天的利润为prices[i] - min_price，其中min_price为前i-1天的最低价格；如果第i天不卖出股票，则前i天的最大利润与前i-1天的最大利润相同。

状态转移方程为：

dp[i] = max(dp[i-1], prices[i] - min_price)

算法步骤如下：

min_price = float('inf')

max_profit = 0
for price in prices:
    if price < min_price:
        min_price = price
    else:
        max_profit = max(max_profit, price - min_price)
return max_profit

时间复杂度：O(n)

3. 实际代码

以下是使用Python实现的动态规划解法：

def maxProfit(prices):

    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
    return max_profit

4. 总结

买卖股票的最佳时机问题是一道经典的动态规划问题，可以通过暴力法和动态规划来解决。

暴力法的时间复杂度为O(n^2)，效率较低，因此在实际代码中我们采用了动态规划的解法。动态规划的时间复杂度为O(n)，且代码更简洁。

使用动态规划解题时，我们需要定义合适的状态和状态转移方程。在本问题中，我们定义了状态dp[i]表示到第i天为止的最大利润，通过不断更新最低价格和最大利润来得到结果。

因此，动态规划是解决买卖股票的最佳时机问题的最优解法。