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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: 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:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
题意
计算买卖股票最大收益，数组是按天数的顺序，要注意顺序的先后。
思路
- 暴力
def maxProfit1(self, prices: List[int]) -> int:
profit = 0
for i in range(len(prices)):
for j in range(i, len(prices)):
if prices[j] - prices[i] > 0:
profit = max(profit, prices[j] - prices[i])
return profit
- 只需记录买进时的最小值，并观察现在买入的减去最小值是否大于之前收益，如果大于则更新收益，如果现在的买入小于最小值则更新最小值。
def maxProfit2(self, prices: List[int]) -> int:
if len(prices) < 1:
return 0
small = prices[0]
profit = 0
for i in range(1, len(prices)):
if prices[i] - small > profit:
profit = prices[i] - small
if prices[i] < small:
small = prices[i]
return profit
