代码如下：
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0:
return 0
if len(prices) == 1:
return 0
minp= prices[0];
profit = 0;
for i in range(len(prices)):
if prices[i] < minp:
minp = prices[i]
else:
profit = max(profit, prices[i] - minp)
return profit
动态规划的思想，每一步都是当前的最优值。代码如下：
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0 or len(prices) == 1:
return 0
best_price = prices[0]
max_profit = 0
for p in prices:
best_price = min(best_price, p)
max_profit = max(max_profit, p - best_price)
return max_profit
