Best Time to Buy and Sell Stock
This coding challenge involves finding the maximum profit from a single buy-sell transaction given a list of stock prices over consecutive days. The key idea is to keep track of the minimum purchase price (buy) seen so far and the maximum profit that can be achieved with each new price encountered.
Steps to Solve:
1. Initialize Variables:
Initialize two variables: profit to track the maximum profit and buy to keep track of the minimum purchase price so far. Set profit to 0 and buy to a very high value (Infinity) to ensure any price will be lower.
2. Iterate Through Prices:
For each price p in the prices array, perform the following checks and updates:
3. Buying Condition:
If p is less than buy, update buy to p. Also, reset sell to a very low value (-Infinity) to ensure the next sell price is higher than the new buy price.
4. Selling Condition:
If p is greater than sell, update sell to p. Update profit to the maximum of the current profit and the difference between sell and buy.
5. Return Profit:
After iterating through all prices, return the maximum profit achieved.
Pseudo Code
Function maxProfit(prices)
Initialize profit to 0
Initialize buy to Infinity
Initialize sell to -Infinity
For each price p in prices
If p < buy
Update buy to p
Reset sell to -Infinity
Else if p > sell
Update sell to p
Update profit to max(profit, sell - buy)
Return profit
EndFunction
Explanation of Solution
The solution effectively scans through the list of prices once (O(n) complexity), updating the buy price whenever a lower price is found. This guarantees buying at the lowest price up to that point. When a higher sell price is encountered, the potential profit (sell - buy) is calculated. If this profit is greater than the current maximum profit, the maximum profit is updated. This approach ensures that the maximum profit possible with a single buy-sell transaction is found, adhering to the constraint that the buy must occur before the sell.