6/23/2017 - 2:09 AM

## 123. Best Time to Buy and Sell Stock III

1. Best Time to Buy and Sell Stock III
``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <= 1:
return 0
#################################
# recd[i] is the max profit of the transactiong that you can make before (including) day i.
recd = [0]*len(prices)
sofarMin = float('inf')
sofarMaxProf = 0
for i in range(len(prices)):
if prices[i] < sofarMin:
sofarMin = prices[i]
elif prices[i] - sofarMin > sofarMaxProf:
sofarMaxProf = prices[i] - sofarMin
recd[i] = sofarMaxProf
##################################
# rev_recd[i] is the max profit of the transaction that you can make after (including) day i.
rev_recd = [0]*len(prices)
sofarMax = -float('inf')
sofarMaxProf = 0
for i in range(len(prices)-1,-1,-1):
if prices[i] > sofarMax:
sofarMax = prices[i]
elif sofarMax - prices[i] > sofarMaxProf:
sofarMaxProf = sofarMax - prices[i]
rev_recd[i] = sofarMaxProf
##################################
maxProf = 0
for i in range(len(prices)):
if recd[i] + rev_recd[i] > maxProf:
maxProf = recd[i] + rev_recd[i]
return maxProf``````