class Solution1(object):
"""
use yes[i] to denote the people is in the condition of holding prices at i-th day, they can buy prices or keep older buy state
use no[i] to denote the people is in the condition of holding no prices at i-th day. If a people is in no state at i-th day, he may also in no state at i-1-th or yes
at i-1-th day and sold it at i-th day
yes array and no array update as follow:
yes[i] = max(yes[i-1], no[i-2] + -prices[i]) (if buy today , yesterday must be no state)
no[i] = max(no[i-1], yes[i-1] + prices[i])
"""
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0: return 0
yes = [0]*len(prices)
no = [0]* len(prices)
yes[0], no[0] = -prices[0], 0
for i in range(1,len(prices)):
yes[i] = max(yes[i-1], no[i-2] - prices[i])
no[i] = max(no[i-1], yes[i-1] + prices[i])
return max(yes[-1], no[-1])
class Solution(object):
"""
Optimize in memory , O(1) space
16 ms, faster than 99.74%
"""
def maxProfit(self, prices):
if len(prices) == 0:return 0
yes_today = -prices[0]
no_today, no_yesterday = 0, 0
for i in range(1, len(prices)):
yes_tmp = yes_today
no_tmp = no_today
yes_today = max(yes_tmp, no_yesterday - prices[i])
no_today = max(no_tmp, yes_tmp + prices[i])
no_yesterday = no_tmp
return max(no_today, yes_today)
