Best Time to Buy and Sell Stock
Problem
You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction.
prices = [8, 3, 6, 4, 9, 5]6def best_profit(prices):
min_so_far = float("inf")
best = 0
for p in prices:
if p < min_so_far:
min_so_far = p
if p - min_so_far > best:
best = p - min_so_far
return bestfunction bestProfit(prices) {
let minSoFar = Infinity;
let best = 0;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minSoFar) minSoFar = prices[i];
const profit = prices[i] - minSoFar;
if (profit > best) best = profit;
}
return best;
}class Solution {
public int bestProfit(int[] prices) {
int minSoFar = Integer.MAX_VALUE;
int best = 0;
for (int p : prices) {
if (p < minSoFar) minSoFar = p;
if (p - minSoFar > best) best = p - minSoFar;
}
return best;
}
}int bestProfit(vector<int>& prices) {
int minSoFar = INT_MAX, best = 0;
for (int p : prices) {
if (p < minSoFar) minSoFar = p;
if (p - minSoFar > best) best = p - minSoFar;
}
return best;
}Explanation
Since you must buy before you sell, the best sell price on any day is paired with the cheapest price you have seen so far. So as we scan left to right, we just remember the lowest price up to now and check the profit if we sold today.
We track two values: min_so_far, the smallest price seen, and best, the largest profit found. For each price p we first update min_so_far, then ask whether p - min_so_far beats our current best.
This single pass is enough because every potential sell day is compared against the cheapest valid buy day before it. We never need to look ahead or try every pair.
Example: prices = [8, 3, 6, 4, 9, 5]. The running minimum drops to 3, and when we reach 9 the profit 9 - 3 = 6 becomes the best. No later day beats it, so the answer is 6.