10. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a stock on day i.
You may make one trade: buy a single share on one day and sell it on a later day. Return the largest profit you can make. If no trade makes money, return 0.
Input: prices = [8,3,6,2,7,4] Output: 5
Explanation: Buy on day 3 at price 2 and sell on day 4 at price 7.
Input: prices = [9,7,4,1] Output: 0
Explanation: The price only falls, so the best choice is not to trade.
Input: prices = [5,1,10,0,8] Output: 9
Explanation: Buying at 0 gives at most 8; buying at 1 and selling at 10 earns more.
Constraints
1 <= prices.length <= 10^50 <= prices[i] <= 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.