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.
思路1：
采取動(dòng)態(tài)規(guī)劃中的Kadane算法，采用兩個(gè)數(shù)分別記取當(dāng)前最大值curMax和截止到現(xiàn)在最大值sofarMax裁眯，以此從1開始遍歷list搂橙。比較0和curMax加上prices[i]-prices[i-1]棵介，以后的處理就和Maximum Subarray類似了贮预。
對(duì)于每一個(gè)階段來(lái)說(shuō)擎椰，我們只關(guān)注一個(gè)狀態(tài)：當(dāng)前元素減去上一元素的值椭懊。對(duì)于每個(gè)階段來(lái)說(shuō)旱爆，值最大的那個(gè)差值，就是局部最優(yōu)解冲泥。在轉(zhuǎn)移過程中，如果上一階段的最優(yōu)解小于0壁涎，則直接重設(shè)為0凡恍；如果不小于0，則只需要在上一階段的局部最優(yōu)解的基礎(chǔ)上怔球，加上下一個(gè)差值即可嚼酝。
思路2：采取兩個(gè)數(shù)保存最小價(jià)格min_prices和最大利潤(rùn)max_profit，依次遍歷list竟坛，如果有比當(dāng)前價(jià)格小的闽巩，賦給min_prices，profit就是price-prize担汤，如果有比當(dāng)前利潤(rùn)大的涎跨，就賦給maxprofit。Python中可以用如下方式表示正負(fù)無(wú)窮：float("inf"), float("-inf")崭歧。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
curMax = sofarMax = 0
for i in xrange(1, len(prices)):
curMax = max(0, curMax + prices[i] - prices[i-1])
sofarMax = max(curMax, sofarMax)
return sofarMax
def maxProfit2(self, prices):
if len(prices) < 2:
return 0
buy, sale, profit = prices[0], 0, 0
for i in xrange(1, len(prices)):
if prices[i] < buy:
buy = prices[i]
elif prices[i] > buy:
sale = prices[i]
if sale - buy > profit:
profit = sale - buy
if sale == 0:
profit = 0
return profit
def maxProfit3(self, prices):
max_profit, min_price = 0, float('inf')
for price in prices:
min_price = min(min_price, price)
print 'min price', min_price
profit = price - min_price
max_profit = max(profit, max_profit)
print 'max profit', max_profit
return max_profit
if __name__ == '__main__':
sol = Solution()
s = [7, 1, 5, 3, 6, 4]
# the expect result is 5 (6-1)
print sol.maxProfit(s)
print sol.maxProfit2(s)
print sol.maxProfit3(s)
s2 = [7, 6, 4, 3, 1]
# the expect result is 0
print sol.maxProfit(s2)
print sol.maxProfit2(s2)
補(bǔ)充：設(shè)置游標(biāo)記取最小價(jià)格隅很，然后比較每個(gè)價(jià)格和這個(gè)最小價(jià)格的差值，其中最大的值就是我們的最大盈利率碾。
def maxProfit4(self, prices):
res = 0
low = float('inf')
for i in xrange(len(prices)):
if prices[i] < low:
low = prices[i]
res = max(res, prices[i]-low)
return res
