Problem

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

题目描述

给定一个股票每天的售价，如果你仅允许完成最多一次交易，求最大的收益。注意你在买入股票之前无法卖出股票。

样例

输入: [7, 1, 5, 3 ,6, 4]
输出: 5
解释: 在第二天的时候购入股票，并且在第五天卖出股票，得到的收益是 6-1=5，且为最大收益。

解法 1

我们将这个问题稍微转换一下，即可变成我们熟悉的问题。由题目所说，我们需要考虑在第 i 天购入股票而在第 j 天卖出股票。我们考虑连续买入卖出情形，即在第 i 天买入，然后在第 i+1 天卖出，再在第 i+1 天买入，在第 i+2 天卖出，…，在第 j-1 天买入，在第 j 天卖出。显然这样获得的收益与原先的收益是一样的。

但是，我们可以很方便的计算每天的收益。例如对于样例中的 [7, 1, 5, 3, 6, 4] 而言，每天的收益是 [-6, 4, -2, 3, -2]，于是我们原先的问题就变成了在这个新数组中求解子数组的最大和问题，这与[Maximum Subarray](https://quicy.notion.site/Maximum-Subarray-60971fce2ebc43c58c793ec85b696616) 一致。

最后要注意的是，如果我们计算出来的最大和小于 0，这时我们的最大收益应为 0，即不买入也不卖出。

参考代码:

class Solution:
    def max_profit(self, prices):
        n = len(prices)
        if n == 0 or n == 1:
            return 0
        profits = [0] * (n-1)
        for i in range(1, n):
            profits[i-1] = prices[i] - prices[i-1]

        res = max(0, profits[0])
        prev = profits[0]
        for i in range(1, n-1):
            prev = max(prev+profits[i], profits[i])
            res = max(res, prev)
        return res

解法 2

我们也可以直接解决这个问题。由于题目要求是完成最多一次交易，那么，我们需要考虑的一个重要变量是当前是否持有股票。我们用两个数组 f、g 来表示第 i 天未完成交易并持有股票的最大收益，第 i 天已完成一次交易并不持有股票的最大收益。最后返回 g[n-1] 即可。那么: