Recursion
Max Profit with 1 Trade
Given a list of stock prices, prices, find the maximum profit you can make.
You can only buy and sell the stock once, or not at all. You can own 1 stock at a time.
There's a tricky greedy algorithm to solve this problem, but using recursion is 10x easier.
In this problem, you can own or not own the stock, or you can sell it, in which case you can't do anything else. You can describe this with 3 states, Not Own, Own, and Sold:
0. Problem
We want the max profit in the Bought and Sold state on day n. We'll sove for these:
1. Recursion
We can look at the arrows that point to each state to get the recursion:
2. Base case
We start out in the Not Own state with 0 profit. The profits in all the other states don't exist yet. We'll set them to -infinity so they don't count towards any computations and get overwritten as soon as possible.
3. Code
We can use Dynamic Programming and "Tabulation+":
Time Complexity O(n). We loop through an array.
Space Complexity O(1). We store 3 variables.
This is the optimal solution. Here are some minor optimizations, if you're curious.
First, N will always be 0, so we can just set it equal to 0 everywhere we see it. Also, you can just return S at the very end since it will always be bigger than N and O on the last day (you always benefit from selling the stock on the very last day). Here's the code for this:
