Medium

Best Time to Buy and Sell Stock II

068

Return the maximum profit from as many buy-sell transactions as you want, holding at most one share at a time.

EXAMPLES

Example 1

Input
{
  "prices": [
    7,
    1,
    5,
    3,
    6,
    4
  ]
}

Output
7

FUNCTION SHAPE

prices: intArray→int

SOLUTION NOTE

Greedy: capture every upward movement. Equivalent to buying every valley and selling every peak.

Reveal reference solution +

pythonREFERENCE

def maxProfit(self, prices: List[int]) -> int:
    return sum(max(0, prices[i] - prices[i-1])
               for i in range(1, len(prices)))

TimeO(n)

SpaceO(1)