Best Time To Buy And Sell Stock

---

Intuition

• To solve the problem brute force, notice that each stock, if bought at that time, can be compared with each subsequent stock, getting the max of the positive difference between the stock bought and sold.
• This same brute force solution can be solved recursively in a top down fashion (Dynamic Programming (Coding)).
  • Each stock bought relies on information in the future to determine the optimal cost if making the decision to buy then.
  • For each index i, you have the choice:
    • Buy at that stock
    • If bought previously, sell
    • Buy at next stock
  • However, this will give a memory limit exceeded error since 2 ${\sum }_i^{n}i$ recursive calls are made for each i.
• For bottom up,
• The optimal solution is to use Sliding Window. Sliding window works here since as long as a previous stock is greater than or equal to a later stock, it cannot be sold for profit. So, via a sliding window, skip such combinations.
• Also, if an left and right, left $<$ right combination is valid, the array in question must be increasing (since otherwise you would encounter a value greater than or equal to prices[right])
  • ex) [2, 3, 4, 1, 5, 6]
    • Anything less than 2 must be encountered via the window.

Complexity

Runtime

$O(N)$ since there are at most 2N iterations

Space

$O(1)$

Code

DP

Bottom Up

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
 
        n = len(prices)
        min_price = prices[0]
        max_profit = 0
 
        for i in range(1, n):
            # Update max_profit if selling today is better than any previous day
            max_profit = max(max_profit, prices[i] - min_price)
            # Update min_price if today's price is lower than any seen before
            min_price = min(min_price, prices[i])
 
        return max_profit

MLE Top Down

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
 
        @cache
        def r(i, bought_price):
            if i >= n:
                return 0
 
            # Buy on next instead, sell, sell on next, bad sale
            return max(r(i + 1, prices[i]), prices[i] - bought_price, r(i + 1, bought_price), 0)
 
        return r(0, prices[0])

Sliding Window

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        res = 0
        left = 0
        for right in range(n):
            while left < right and prices[left] >= prices[right]:
                left += 1
            
            res = max(res, prices[right] - prices[left])
 
        return res

TLE

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        n = len(prices)
        for i in range(n):
            top = max(prices[i + 1:], default=0)
            res = max(res, top - prices[i])
 
        return res

Notes

Cards

START Basic Front: Best Time To Buy And Sell Stock Back: END

---

References

• Best Time To Buy And Sell Stock