买卖股票

Buy and Sell Stock

专题: Algorithmic Programming / 算法编程
难度: L2
来源: OpenQuant

题目详情

给定一个股票价格数组，其中 $\textrm{prices}[i]$ 表示某只股票在第 $\textrm{ith}$ 天的价格。

你想通过只进行一次交易来使利润最大化：选择某一天买入一股股票，并在未来某个不同的日期卖出。

请编写一个 Python 程序，返回这笔交易所能获得的最大利润。如果无法获得任何利润，则返回 0。

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
# Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
# Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
# Explanation: In this case, no transactions are done and the max profit = 0.

请补全下面的函数来完成程序：

from typing import List

def buy_and_sell_stock(prices: List[int]) -> int:
   """Write your code here"""
   return None

You are given an array of stock prices where $\textrm{prices}[i]$ is the price of a given stock on the $\textrm{ith}$ day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Write a python program that will return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
# Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
# Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
# Explanation: In this case, no transactions are done and the max profit = 0.

Fill in the function below to complete your program:

from typing import List

def buy_and_sell_stock(prices: List[int]) -> int:
   """Write your code here"""
   return None

解析

为了解这道题，我们先从朴素解法出发，再逐步优化。起初，我们知道对于每一天 $i$ ，都有两个选择：买入股票或不买入。是否值得在第 $i$ 天买入，取决于未来某一天卖出时最多能赚多少。用数学形式表示为：

\begin{equation} \textrm{P}(i) = \max ( \{\textrm{stocks[j]} - \textrm{stocks[i]}, \ \textrm{stocks[j+1] - stocks[i]} \ , ..., \textrm{stocks[n]} - \textrm{stocks[i]} \}), \forall j \gt i \end{equation}

本质上，对于每个价格 $\textrm{stocks[i]}$ ，我们都想知道未来能以多高的价格卖出，从而获得最大利润。最直接的方法是使用双重循环：对于每个买入日 $i$ ，在后续的 $i+1 ... n$ 中寻找能达到的最大利润。

朴素解法

时间复杂度： $O(n^2)$ ，其中 $n$ 是股价天数。
空间复杂度： $O(1)$

def buy_and_sell_stock(prices: List[int]) -> int:
    max_profit = 0

    for i in range(len(prices)):
        buy_price = prices[i] # purchase the stock on day i
        for j in range(i + 1, len(prices)):
            sell_price = prices[j] # sell the stock on day j
            max_profit = max(sell_price - buy_price, max_profit) # calculate max profit

    return max_profit

虽然上面的代码可以得到正确答案，但时间复杂度是二次的。为了进一步优化，我们需要换个角度看问题。与其把每一天 $i$ 看作买入日，不如把它看作卖出日。这样一来，对每个日期 $i$ ，我们只需要知道此前见过的最低买入价，因为这就是能在今天卖出时获得最大利润的买入价。同时，我们还可以跟踪每个卖出日对应的最大利润，即“今天卖出能得到的利润”和“前一天之前的最大利润”两者中的较大值。

动态规划

时间复杂度： $O(n)$ ，其中 $n$ 是股价天数。
空间复杂度： $O(n)$ ，其中 $n$ 是股价天数。

from typing import List

def buy_and_sell_stock(prices: List[int]) -> int:
    min_stock_price = prices[0] # cheapest price at which we could have purchased a stock
    daily_max_profit = [0] * len(prices) # max obtainable profit each day

    for i in range(1, len(prices)):
        max_profit[i] = max(prices[i] - min_stock_price, max_profit[i-1])
        min_stock_price = min(min_stock_price, prices[i])

    return max_profit

最后还能再做一次优化：把 `daily_max_profit` 数组替换成一个变量，只记录截至当前为止的最大利润。

优化后的动态规划

时间复杂度： $O(n)$ ，其中 $n$ 是股价天数。
空间复杂度： $O(1)$

from typing import List

def buy_and_sell_stock(prices: List[int]) -> int:
    min_stock_price = prices[0]  # Keep track of the lowest price we can purchase a stock
    max_profit = 0               # Keep track of the maximum profit we can earn

    for i in range(1, len(prices)):
        max_profit = max(prices[i] - min_stock_price, max_profit)
        min_stock_price = min(min_stock_price, prices[i])

    return max_profit

Original Explanation

To solve this question, let's first consider a naive solution and build our way up to a more optimized version. To start, we know that for each day $i$ we have to choose from one of two options: purchase the stock or don't purchase the stock. The criteria for purchasing a stock is based on the maximum amount we can earn by selling that same stock on a future date. Mathematically, this can be represented as:

\begin{equation} \textrm{P}(i) = \max ( \{\textrm{stocks[j]} - \textrm{stocks[i]}, \ \textrm{stocks[j+1] - stocks[i]} \ , ..., \textrm{stocks[n]} - \textrm{stocks[i]} \}), \forall j \gt i \end{equation}

In essence, for each price $\textrm{stocks[i]}$ we want to find the maximum price we can sell this stock for in the future. The trivial method for accomplishing this is to use a double for loop. For each stock price $\textrm{stock[i]}$ we search for the max profit we can achieve in following days $i+1 ... n$

Trivial Solution

Time Complexity: $O(n^2)$ where $n$ is the number of days worth of stock prices we have.
Space Complexity: $O(1)$

def buy_and_sell_stock(prices: List[int]) -> int:
    max_profit = 0

    for i in range(len(prices)):
        buy_price = prices[i] # purchase the stock on day i
        for j in range(i + 1, len(prices)):
            sell_price = prices[j] # sell the stock on day j
            max_profit = max(sell_price - buy_price, max_profit) # calculate max profit

    return max_profit

While the code above does allow us to arrive at the correct solution, we see that it is quadratic in time complexity. To reduce the time complexity of this solution we need to change the frame by which we view the problem. Instead of considering each day $i$ as the purchase date of the stock, let's consider this as the sale date of the stock. Now, for each date $i$ all we need to know is the minimum purchase price we've seen thus far because that would be price at which we would have purchased the stock to obtain the largest possible profit. In addition, we'll keep track of the max profit on each sale date, which will be determined by the max profit we could have obtained today vs the max profit we could have obtained by selling the stock on the previous day.

Dynamic Programming

Time Complexity: $O(n)$ where $n$ is the number of days worth of stock prices we have.
Space Complexity: $O(n)$ where $n$ is the number of days worth of stock prices we have.

from typing import List

def buy_and_sell_stock(prices: List[int]) -> int:
    min_stock_price = prices[0] # cheapest price at which we could have purchased a stock
    daily_max_profit = [0] * len(prices) # max obtainable profit each day

    for i in range(1, len(prices)):
        max_profit[i] = max(prices[i] - min_stock_price, max_profit[i-1])
        min_stock_price = min(min_stock_price, prices[i])

    return max_profit

As one final optimization, we can replace the 'daily_max_profit' array with a variable that holds the max profit achieved thus far.

Optimized Dynamic Programming

Time Complexity: $O(n)$ where $n$ is the number of days worth of stock prices we have.
Space Complexity: $O(1)$

from typing import List

def buy_and_sell_stock(prices: List[int]) -> int:
    min_stock_price = prices[0]  # Keep track of the lowest price we can purchase a stock
    max_profit = 0               # Keep track of the maximum profit we can earn

    for i in range(1, len(prices)):
        max_profit = max(prices[i] - min_stock_price, max_profit)
        min_stock_price = min(min_stock_price, prices[i])

    return max_profit