正文

【LeetCode OJ】Best Time to Buy and Sell Stock

IP云
IP云V管理员/5 阅读
09/29
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Problem Link:

http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/

We solve this problem using DP algorithm, which only scans the prices list once. So the algorithm is in O(n) where n is the length of prices list.

By given a list prices[0:n], we represent a trasaction as (b,s) where 0<=b<=s is the day to buy and b<=s<=n-1 is the day to sell.

However, we do not need a O(n) table to store all local optimal solution. Instead, We use only three variables to keep track of local optimal solution.

Suppose prices[0:i] have been scanned, we maitain following variables:

  • l - The day with the lowest prices in prices[0:i]
  • b - The buy day of the local optimal transaction for prices[0:i]
  • s - The sell day of the local optimal transaction for prices[0:i]

We initialize l = b = s = 0, and for each i = 1...n-1, we update by following steps:

  1. If prices[i] < prices[l], then update the lowest price day l.
  2. We update b = l and s = i if one of the following conditions is satisfied.
    1. prices[i] > prices[s]
    2. prices[s] - prices[b] < prices[i] - prices[l]

The following code in python is accepted by oj.leetcode.com.

class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
"""
DP solution: suppose already have following informations in prices[0:i]:
1. Lowest price
2. Current profit presented by the buy price and the sell price
Then for prices[0:i+1], we can update as follows:
If prices[i] > prices[s]:
sell_price = prices[i]
buy_price = lowest_price
elif prices[i]-lowest_price > prices[s] - prices[b]:
buy_price = lowest_price
sell_price = prices[i]
elif prices[i] < lowest_price:
lowest_price = prices[i]
After scan all prices, we return sell_price - buy_price
The initial case:
lowest_price = prices[0]
buy_price = prices[0]
sell_price = prices[0]
And we scan prices from prices[1].
"""
# Special case: prices == []
if not prices:
return 0
# Initialize with prices[0]
b = s = l = 0
# Scan from i = 1 to n-1
for i in xrange(1, len(prices)):
if prices[i] < prices[l]:
l = i
elif prices[i] > prices[s] or prices[s] - prices[b] < prices[i] - prices[l]:
s = i
b = l
return prices[s] - prices[b]