Understanding the Problem
We are given an array of stock prices, where each element represents the price of a stock on a particular day. Our goal is to find the best day to buy and the best day to sell the stock to maximize profit. However, we are allowed to make this transaction only once, and we must buy the stock before we sell it.
In simple terms, we want to choose two days: one for buying and one for selling. The profit is the difference between the selling price and the buying price. If no profit is possible (i.e., prices only go down), we return 0.
Step-by-Step Solution with Explanation
1. Track the Minimum Price
As we go through the list, we will keep track of the lowest price we’ve seen so far. This will represent the best day to buy so far.
2. Calculate Profit
At each step, we calculate the profit if we were to sell the stock on that day, using the lowest price we've seen before. If this profit is greater than the best profit we’ve recorded, we update our best profit.
3. Use Example for Better Understanding
Let’s understand this with a beginner-friendly example: [7, 1, 5, 3, 6, 4]
- Day 1: Price = 7 → minPrice = 7
- Day 2: Price = 1 → minPrice = 1 (found a cheaper buy)
- Day 3: Price = 5 → profit = 5 - 1 = 4 → maxProfit = 4
- Day 4: Price = 3 → profit = 3 - 1 = 2 → maxProfit remains 4
- Day 5: Price = 6 → profit = 6 - 1 = 5 → maxProfit = 5
- Day 6: Price = 4 → profit = 4 - 1 = 3 → maxProfit remains 5
Result: Best profit is 5 (Buy at 1, sell at 6)
Handling Edge Cases
Case 1: Prices Only Go Down
Example: [7, 6, 4, 3, 1]
The price keeps dropping. Any buy-sell pair results in a loss. So, the maximum profit is 0.
Case 2: Constant or Steady Increase
Example: [1, 2, 3, 4, 5]
Here, buying at day 1 and selling at day 5 gives the best result: profit = 5 - 1 = 4.
Case 3: Single Price
Example: [10]
We can’t sell if we buy on the only day available. So, the profit is 0.
Case 4: Empty Array
There are no prices at all, so no transaction can be made. The answer is 0.
Comments
Loading comments...