class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
#cash1:cash on hand if i sell today
#cash2:cash on hand if i do nothing today
#start with 0 cash on hand
cash1,cash2=0,0
for i in xrange(1,len(prices)):
cash1_yesterday=cash1
#2 scenarios:
#1.i just sold the stock yesterday, so i need to buy back yesterday and sell today.(postpone the selling from yesterday to today)
#2. did nothing yesterday (didnt have a stock), so need to buy today and sell today(equal to do nothing)
cash1=max(cash1_yesterday-prices[i-1]+prices[i],cash2)
cash2=max(cash1_yesterday,cash2)
return max(cash1,cash2)
state machine
three state
s0: not holding a stock, free to trade. actions: a1 stay put->s0; a2 buy a stock->s1
s1: holding a stock, free to buy. action: a1 stay put ->s1; a2 sell a stock->s2
s2: not holding a stock, cool down period not able to trade. action: a1 rest ->s0
s0[i]=max(s0[i-1],s2[i-1])
s1[i]=max(s0[i-1]-p[i],s1[i-1])
s2[i]=s1[i-1]+p[i]
on day i, max profit = max(s0[i],s2[i])
initial condition:
s0[0]=0
s1[0]=-p[0]
s2[0]=s2 came from s1 by selling, without price information, assign s2[0] as -inf
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
#cash1:cash on hand if i sell today
#cash2:cash on hand if i do nothing today
#start with 0 cash on hand
if not prices: return 0
days=len(prices)
s0=[0]*days
s1=s0[:]
s2=s0[:]
#initialize
s1[0]=-prices[0]
s2[0]=-float('inf')
for i in xrange(1,days):
s0[i]=max(s0[i-1],s2[i-1])
s1[i]=max(s0[i-1]-prices[i],s1[i-1])
s2[i]=s1[i-1]+prices[i]
return max(s0[days-1],s2[days-1])
