# Best Time to Buy and Sell Stock

ArrayPrefix SumDP

## # Solution

The brute-force solution w/ $O(n^2)$ time would be to search for max profit w/ a nested for loop iterating over buy and sell dates and updating max profit.

All solutions below have complexities of linear time and constant space.

### # Prefix Min

• max profit: the difference price - prefix_min_price.
• price: current price

If current price is min so far, update the prefix_min_price to price. Else if the current price is a max so far, update max_profit to price - prefix_min_price.

def maxProfit(self, prices: List[int]) -> int:
prefix_min_price, max_profit = sys.maxsize, 0

for price in prices:
if price < prefix_min_price:
prefix_min_price = price
elif price - prefix_min_price > max_profit:
max_profit = price - prefix_min_price
return max_profit

1
2
3
4
5
6
7
8
9

Or could just use max and min instead of if/else statements.

def maxProfit(self, prices: List[int]) -> int:
prefix_min_price, max_profit = sys.maxsize, 0

for price in prices:
prefix_min_price = min(price, prefix_min_price)
max_profit = max(max_profit, price - prefix_min_price)
return max_profit

1
2
3
4
5
6
7

### # Suffix Max

Updating suffix_max_price rather than the prefix_min_price also works in this problem.

def maxProfit(self, prices: List[int]) -> int:
suffix_max_price, max_profit = -sys.maxsize, 0

for i in reversed(range(len(prices))):
suffix_max_price = max(suffix_max_price, prices[i])
max_profit = max(max_profit, suffix_max_price - prices[i])
return max_profit

1
2
3
4
5
6
7