# O(n) runtime, O(1) memory Python solution

• The key intuition is that one of the trade must involve the highest price.

Step 1:

Calculate the global best trade. Note the trade sequence is prices [i,j].

Note that the highest price is j

Step 2:

If it is the first trade, then the second trade profit is calculated by prices[j+1:]

If it is the second trade, then there are two options:

(1) the first trade happens before the current best trade, calculate the profit by prices[0:i]

(2) the first trade happens within the current trade. The key intuition here is that the profit must be the maximum running loss. It can be calculated by reverse the price sequence, aka prices[j,i,-1]

I am sure my code can be improved upon. As it stands, it beats 73%

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""

# Since there are at most two trades, the trade must happen at two non-overlapping period
# therefore, such scheme must maximize the profit over two period.

# Method 1:
# cut the history by 2: n-1 ways
# within each segment, apply the one trade algorithm
# Runtime is O(n^2), memory O(1)
# Too costly, run time out
#################################################
# Method 2:
# One trade must involve sell on the highest price.

# if it is the first trade, split the history from there
# if it is the second trade, find the largest cumulative loss in the single trade, and the profit will be profit + cumulative loss
# the largest loss can be found by reversing the sequence of prices

# Runtime O(n), memory O(1)
# 73%

if prices == []:
return 0,[]

profit = 0
book = 0

# need to code the start and end idx
trade_idx = [0,1]  # start & end
best_profit = 0

T = len(prices)
for i in range(T-1):
delta = prices[i+1] - prices[i]
if book + delta <0:
# switch position if the cost basis becomes negative
# reset book and start_idx
profit = max(book,profit)
# update the best history
if profit > best_profit:
best_profit = profit
# start anew
book = 0
else:
book += delta
if book >= profit:
profit = book
if profit > best_profit:
best_profit = profit

##############################
# deal with outlier
n = len(prices)
if n<=1:
return 0

if max_idx != n:
else: