Best Time to Buy and Sell Stock
Choose one day to buy a stock and a later day to sell it. Find the largest possible profit. You may choose not to trade.
Work through the cases
3 examplesInput notation
Daily prices as nonnegative integers separated by spaces.Expected result
The maximum profit, or 0.Case 1
Input
9 2 6 1 7
Expected output
6
Case 2
Input
7 5 3
Expected output
0
Case 3
Input
5
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
One buy and one sell; trying every pair is O(n^2) and n can reach 10^5. For a fixed sell day the best buy is the minimum price before it. Scan while keeping the prefix minimum, update the answer by today's price minus that minimum, then fold today into the prefix.
We can enumerate each element of the array nums as the selling price. Then we need to find a minimum value in front of it as the purchase price to maximize the profit.
Therefore, we use a variable mi to maintain the prefix minimum value of the array nums. Then we traverse the array nums and for each element v, calculate the difference between it and the minimum value mi in front of it, and update the answer to the maximum of the difference. Then update mi = min(mi, v). Continue to traverse the array nums until the traversal ends.
Finally, return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
class Solution {
public int maxProfit(int[] prices) {
int ans = 0, mi = prices[0];
for (int v : prices) {
ans = Math.max(ans, v - mi);
mi = Math.min(mi, v);
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.