712197. Stock Buy and Sell – Max one Transaction Allowed
Easy
Stock Buy and Sell – Max one Transaction Allowed
Summary
The problem is about finding the maximum profit that can be achieved by buying and selling a stock at most once. The input is an array of stock prices, and the goal is to find the best time to buy and sell the stock to maximize the profit.
Detailed Explanation
To solve this problem, we'll use a greedy algorithm. We'll iterate through the array of stock prices and keep track of the minimum price we've seen so far (min_price) and the maximum profit we can achieve by selling at that price (max_profit).
Here's a step-by-step breakdown:
- Initialize min_price to the first element of the array, and max_profit to 0.
- Iterate through the array:
- If the current price is less than min_price, update min_price.
- Calculate the potential profit by subtracting min_price from the current price.
- Update max_profit if the potential profit is greater than the current max_profit.
- Return max_profit as the maximum possible profit.
Here's a diagram to illustrate the algorithm:
+--------+ +--------+
| Buy | | Sell |
+--------+ +--------+
|
v
+--------+ +--------+
| Min | | Max |
| Price | | Profit |
+--------+ +--------+
Time complexity: O(n), where n is the length of the input array. Space complexity: O(1), as we only use a few variables to store our state.
Optimized Solutions
Java
int maxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else {
int potentialProfit = price - minPrice;
if (potentialProfit > maxProfit) {
maxProfit = potentialProfit;
}
}
}
return maxProfit;
}