Best Time to Buy and Sell Stock
A reseller tracks the price of one pair of limited-edition sneakers on a marketplace, where prices[i] is the price on day i. They may make a single round trip: buy one pair on some day and sell it on a strictly later day.
Return the largest profit that round trip can earn. If every possible trade would lose money or only break even, the reseller does not trade at all, and the answer is 0.
Input: prices = [12,9,15,10,18,8] Output: 9
Explanation: Buy on day 1 for 9 and sell on day 4 for 18. The cheapest price, 8, falls on the last day, so nothing can be sold after it.
Input: prices = [30,25,25,20] Output: 0
Explanation: The price never rises, so no trade makes money.
Input: prices = [4,11,2,8] Output: 7
Explanation: Buying at the lowest price, 2, earns only 6; buying at 4 and selling at 11 earns 7.
Constraints
pricescovers between 1 and 10^5 days.- Every price is an integer from 0 to 10^4.
💡 Hint 1
Checking every buy/sell pair is O(n²). If you decide to sell on day i, which buy day is best?
💡 Hint 2
The best buy day for selling on day i is the cheapest day before it. Track that running minimum as you scan.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Scan the prices once, keeping the lowest price seen so far. On each day, selling today would earn price - minSoFar; keep the best such value. Update the minimum after computing the profit, so you never sell before you buy. If prices only fall, the best profit stays 0.
function maxProfit(prices) {
let minPrice = Infinity;
let best = 0;
for (const p of prices) {
best = Math.max(best, p - minPrice);
minPrice = Math.min(minPrice, p);
}
return best;
}class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, best = 0;
for (int p : prices) {
if (p > minPrice) best = Math.max(best, p - minPrice);
minPrice = Math.min(minPrice, p);
}
return best;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} prices
* @return {number}
*/
function maxProfit(prices) {
}Run your code to see results here.