Maximum Profit From One Buy and One Sell
Solve this Problemprices where prices[i] is a stock's price on day i, you may buy on one day and sell on a later day to maximize profit. A sale must happen strictly after the purchase. Return the maximum profit achievable, or 0 if no profitable trade exists.
This looks like a search over every pair of days, but for any fixed sell day, only ONE earlier day could possibly be the best buy day: whichever one had the lowest price. Tracking that running minimum turns an O(n²) search into a single O(n) pass — and it's really the same Kadane's algorithmKadane's AlgorithmA single pass that, at each position, decides whether to extend the current running result or restart from here — used to find the best contiguous run in an array in O(n). idea in disguise: the day-to-day price differences form an array, and this problem's answer is exactly its maximum-sum contiguous subarray.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ prices.length ≤ 10⁵ - ◆
0 ≤ prices[i] ≤ 10⁴
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int maxProfit(int[] prices) { |
| 3 | int minPrice = prices[0]; |
| 4 | int maxProfit = 0; |
| 5 | for (int i = 1; i < prices.length; i++) { |
| 6 | maxProfit = Math.max(maxProfit, prices[i] - minPrice); |
| 7 | minPrice = Math.min(minPrice, prices[i]); |
| 8 | } |
| 9 | return maxProfit; |
| 10 | } |
| 11 | } |
| 12 |
70Start minPrice at prices[0] = 7, and maxProfit at 0. Walk through the rest of the prices once.
Approach & Solutions
Brute Force
BruteTry every pair of a buy day and a later sell day, and keep the best profit seen. Correct, but most of these pairs are wasted work — for a fixed sell day, only the lowest price seen before it could ever be the best buy day.
O(n²)O(1)1class Solution {
2 public int maxProfit(int[] prices) {
3 int maxProfit = 0;
4 for (int i = 0; i < prices.length; i++) {
5 for (int j = i + 1; j < prices.length; j++) {
6 maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
7 }
8 }
9 return maxProfit;
10 }
11}Optimal — Single Pass, Track Minimum So Far
OptimalWalk through the prices once, keeping track of the lowest price seen so far. At each day, the best profit from selling today is today's price minus that running minimum — compare it against the best profit found so far, then update the minimum if today's price is a new low. This is Kadane's "extend or restart" idea in disguise: it's really tracking the maximum subarray sum of the day-to-day price differences.
O(n)O(1)1class Solution {
2 public int maxProfit(int[] prices) {
3 int minPrice = prices[0];
4 int maxProfit = 0;
5 for (int i = 1; i < prices.length; i++) {
6 maxProfit = Math.max(maxProfit, prices[i] - minPrice);
7 minPrice = Math.min(minPrice, prices[i]);
8 }
9 return maxProfit;
10 }
11}