假设您有一个数组，其中的ith元素是第i天给定股票的价格。
如果你只被允许完成至多一笔交易（即买一份，卖一份股票），设计一个算法来找到最大利润。
请注意，在购买股票之前，您不能出售股票。
Example 1:
<strong>Input:</strong> [7,1,5,3,6,4] <strong>Output:</strong> 5 <strong>Explanation:</strong> 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:
<strong>Input:</strong> [7,6,4,3,1] <strong>Output:</strong> 0 <strong>Explanation:</strong> In this case, no transaction is done, i.e. max profit = 0.
解法
具体的逻辑说明在代码备注里面
class Solution:
def maxProfit(self, prices: List[int]) -> int:
#如果当前列表长度小于2那么直接返回结果，因为你没有任何交易机会
if len(prices)<2:
return 0
#我们需要三个变量记录，min_index最小买入时间索引，
#同理最大，profit记录最大利润
min_index=0
max_index=0
profit=0
#循环遍历数据
for ind in range(1,len(prices)):
#判断当前的价格大于历史最高价
if prices[ind]>prices[max_index]:
max_index=ind
#计算当前的利润
curr_profit=prices[max_index]-prices[min_index]
#如果利润大于历史利润则使用当前利润
if curr_profit>profit:
profit=curr_profit
#获取最小买入价格，如果最小买入时间索引大于
#最大卖出索引，则需要对最大卖出索引处理
elif prices[ind]<prices[min_index]:
min_index=ind
if min_index>max_index:
max_index=min_index
return profit
