122. Best Time to Buy and Sell Stock II

# Easy

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

Time complexity = $O(n)$ , space complexity = $O(1)$