# Best Time to Buy and Sell Stock

## Question in Human Language

This question asks you to pick two numbers from a list where the one on the left should be as much smaller than the one on the right as possible.

For INHUMAN description, please check it out on LeetCode

## Thought No. 1

Simply put, I want find the minimum in a range, and find a maximum in a range. We then realize that find the maximum or minimum in a range is easy, but which range should we use? Hmmm… How about every possible range? Right, we can use a `for loop` to cut the prices list in evert possible ways.

### Implementations

The steps are:

1. Iterate the indices of the prices
1. Split the prices into two lists (left and right of the current index)
2. Find the minimum of the left list
3. Find the maximum of the right list
4. Calculate the difference between the two as the profit
5. Update the global maximum profit
2. Return the global maximum profit if it is possible, otherwise, return zero

#### Python Ver. 1

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_profit = 0
for i in range(1, len(prices)):
max_profit = max(max_profit, max(prices[i:]) - min(prices[:i]))
return max_profit
``````

### Review

As you have probably noticed, this solution results in a `Time Limit Exceeded`. Why is that? Well, although it may look like a `O(n)` complexity, it is actually a `O(n^2)` because both `max` and `min` are of `O(n)` complexity (how can you know the maximum or minimum if you haven’t look though the entire list?). Can we do better? ## Thought No. 2

What if YOLO, You Only Look (through the list) Once? If so, you need to remember the maximum and minimum in order where in order is very tricky. We can go backwards through prices assuming that we always buy at current time and sell at the seen maximum and keep track of the global maximum profit.

### Implementations Let’s assume that we are going backwards through the prices, and use a variable to keep track of the maximum potential selling price we have seen so far, another variable to keep track of the maximum profit we have seen so far.

Let’s assume the values in the graph are: `[3, 2, 3, 4, 5, 6, 7, 6]`.

Now, let’s go backwards through prices step by step and see why that gives us the maximum profit.

current index in prices price maximum potentail selling price current profit max profit
not started none 0 (initialize) 0 (initialize) 0 (initialize)
7 6 6 (because 6 > 0) 6 - 6 = 0 0
6 7 7 (because 7 > 6) 7 - 7 = 0 0
5 6 7 (because 7 > 6) 7 - 6 = 1 1 (because 1 > 0)
4 5 7 (because 7 > 5) 7 - 5 = 2 2 (because 2 > 1)
3 4 7 (because 7 > 4) 7 - 4 = 3 3 (because 3 > 2)
2 3 7 (because 7 > 3) 7 - 3 = 4 4 (because 4 > 3)
1 2 7 (because 7 > 2) 7 - 2 = 5 5 (because 5 > 4)
0 3 7 (because 7 > 3) 7 - 3 = 4 5 (because 4 < 5)

The steps are:

1. Iterate backwards through prices
1. Set maximum seen prices as potential selling price
2. Calculate the profit based on seen maximum and current price
3. Update the global maximum profit
2. Return the global maximum profit We iterate backwards because it’s hard in Python3 to initialize a minimum value. You can find why that is here

#### Python Ver. 1

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
current_max = 0
max_profit = 0
"""
step 1: iterate backwards through prices
"""
for p in prices[::-1]:
"""
step 1.1: update seen maximum price
"""
current_max = max(current_max, p)
"""
step 1.2: calculate current profit
step 1.3: update global maximum profit
"""
max_profit = max(current_max - p, max_profit)
"""
step 2: return global maximum profit
"""
return max_profit
``````

### Review

Hooray! Accepted! Well done! 