122. Best Time to Buy and Sell Stock II
Solution
-
Keep a strictly increasing stack.
-
When a decreased element come in, add the profit that can be earned from the stack, and clean up the stack.
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
stack = []
profit = 0
for p in prices:
if stack:
if stack[-1] <= p:
stack.append(p)
else:
profit += stack[-1] - stack[0]
stack = [p]
else:
stack = [p]
if stack:
profit += stack[-1] - stack[0]
return profit