Tricky. Accumulate profit(each peak-valley) must be more than less transactions. So just compute accumulate profit.
技巧在于如何找出每个valley-peak的组合
class Solution:
def maxProfit(self, prices: List[int]) -> int:
valley = prices[0]
peak = prices[0]
maxprofit = 0
i = 0
while i < len(prices) - 1: # very important, otherwise enter dead loop, eg, [7,1,5,3,6,4], stuck at peak=4 and valley=4
# find valley
while i < len(prices)-1 and prices[i] >= prices[i+1]:
i += 1
valley = prices[i]
# find peak just following the valley
while i < len(prices)-1 and prices[i] <= prices[i+1]:
i += 1
peak = prices[i]
# accumulate maxprofit
maxprofit += peak - valley
print(peak, valley)
return maxprofit