問題描述

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]

Output: 5

max. difference = 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

In this case, no transaction is done, i.e. max profit = 0.

補充說明：

模擬一個股票系統(tǒng)，給定一個列表，這個列表對應(yīng)的是每日的價格，然后設(shè)計一個算法，從中找到哪一天買入，哪一天賣出能夠獲取最大利潤。這里并不關(guān)注哪日，而是只要輸出最大利潤值。

方案分析

1. 作為最簡單的思路，所有人都能想到時間復(fù)雜度為O(n**2)的解決方案——遍歷兩次，保存最大利潤值。實現(xiàn)沒問題，但不滿足leetcode的時間限定。
2. 從時間復(fù)雜度上下手，這個問題可以轉(zhuǎn)換為找到最大賣出價格和找到最小買入價格的問題。定義兩個變量，表示買入價格和利潤，從頭開始遍歷。如果第二天的價格比第一天的低，設(shè)定為買入價格；這個價格和買入價格相減，并且這個利潤大于保存的利潤，更新。只需要一輪就可以求得最大利潤。

python實現(xiàn)

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0
        if prices:
            buy_price = prices[0]
            for price in prices[1:]:
                buy_price = min(buy_price, price)
                profit = max(profit, price-buy_price)

        return profit