Best Time to Buy and Sell Stock
EasyThe problem
The list prices holds a stock's price on each day. You may buy on one day and sell on a LATER day, only once. Return the biggest profit you can make, or 0 if you cannot make any profit.
- Example 1Input: prices = [3, 8, 2, 6]Output: 5
Buy at 3 on day 0 and sell at 8 on day 1: profit 5. (Buying at 2 and selling at 6 only gives 4.)
- Example 2Input: prices = [9, 7, 4, 1]Output: 0
The price only goes down, so it is best not to trade at all.
- 1 ≤ prices.length ≤ 100,000
- 0 ≤ prices[i] ≤ 10,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
You must buy before you sell. As you walk the days, what single number must you remember?
The idea
Track the lowest price so far; at each day the best profit is price − lowest; keep the maximum.
Target: O(n) time, O(1) space
Go function shape
func maxProfit(prices []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// MaxProfit: the best sale on day i uses the cheapest price BEFORE day i, so remember the minimum so far.
func MaxProfit(prices []int) int {
best, lowest := 0, 1<<60
for _, p := range prices {
lowest = min(lowest, p)
best = max(best, p-lowest)
}
return best
}