https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
pointer を2つ使う。 left が right より低い時点で売る可能性あり。 max_profit に最大の profit を格納。
right の pointer は右に移動し続け
left の pointer は prices[l] が prices[r] より大きい際に、 left の pointer を right の pointer の位置に移動する。
Time complexity: O(n)
Mem complexity: O(1)
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
l, r = 0, 1
max_profit = 0
while r < len(prices):
if prices[l] < prices[r]:
profit = prices[r] - prices[l]
max_profit = max(max_profit, profit)
else:
l = r
r += 1
return max_profit