Running Minimum
Track the lowest price so far and evaluate profit at each step.
0 of 3 problems solved
Running Minimum
Track the lowest price so far and evaluate profit at each step.
- •Am I scanning prices from left to right?
- •Do I only need the cheapest value seen so far?
- •Can I update profit in one pass?
This problem is not really about buying and selling. It is about remembering one useful fact while you scan the array: the cheapest price so far. Every new price asks a simple question: 'If I sold today, how much profit would I make from the cheapest day I have seen?' That means you never need to test every buy day against every sell day. One pass is enough.
Keep two memories only: the lowest price so far and the best profit so far.
- 1Start with the first price as the lowest price seen so far.
- 2Move through the array one day at a time.
- 3For each price, compute profit = current price minus lowest price so far.
- 4Update the best profit if that profit is better, then update the lowest price if today's price is smaller.
Many beginners try every buy day against every sell day. That works, but it ignores the fact that you only need the cheapest earlier price.
Best Time to Buy and Sell Stock II
Unlike one transaction, any positive daily difference is profit. Sum every consecutive up-day without tracking exact buy/sell positions.
Best Time to Buy and Sell Stock III
Track four states at each price: after first buy, after first sell, after second buy, after second sell. Each state updates from the previous one.