DSA-146 · Dominance of the cheapest strictly earlier buy price
Best Time to Buy and Sell Stock — One Transaction
Starter · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 87394 deterministic checks. Learner drafts are not executed.
Understand the problem
Given daily prices, return the greatest profit from at most one transaction that buys on one day and sells on a strictly later day. Choosing no transaction is allowed and yields zero.
- prices is a non-null int[] of length 0..100000 with nonnegative signed-int entries. Null throws NullPointerException; excessive length or a negative entry throws IllegalArgumentException. Validate every price before returning.
- Return a long profit and preserve the array. Empty or singleton input returns zero. A decreasing or constant sequence also returns zero because choosing no transaction is permitted. Buying must precede selling strictly.
- There are no fees, cooldowns, short sales, repeated transactions, or position output. Each price is an exact integer. The profit bound is MAX_VALUE under these nonnegative int prices, and the implementation widens before subtraction rather than depending on an implicit int-range assumption.
Examples
Input:
prices=[7,1,5,3,6,4]
Output:5Buy at one on day one and sell at six on day four.
Input:
prices=[7,6,4,3,1]
Output:0Every legal transaction loses; doing nothing wins.
Input:
prices=[2,4,1]
Output:2The cheapest overall price occurs too late to buy for the earlier sale.
Before you start
- Chronological index constraints
- Running extrema and dominance arguments
Recognize the structure
Fix a possible selling day. Every earlier buy has the same sale price, so a more expensive earlier buy is dominated by the cheapest earlier buy. Keep that prefix minimum and a separate best profit over all selling days. This differs from unlimited trading, where summing every positive daily difference is permitted. Here multiple profitable swings cannot be combined into one answer.
Try before revealing
Hint 1
If the selling day is fixed, which earlier buying price is best?
Hint 2
Can any higher earlier price beat the prefix minimum on a future sale?
Hint 3
Evaluate today’s sale against the old minimum, update the best, then include today in the minimum.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate every chronological buy/sell pair
Inspect each pair buy<sell and maximize the widened price difference against zero. This O(n²)-time, O(1)-space method directly enforces the temporal constraint and no-trade option. The test oracle scans backward with the maximum strictly later selling price, evaluating possible buys instead of reusing the reference’s minimum-earlier-buy recurrence. Exhaustive arrays compare all three methods; the 100000-day stress case uses the linear method only.
Improve the baseline
Seed a real earlier buy and an optional-trade best
If the array is empty, return zero. Otherwise minimum=prices[0] describes the only buy available before day one, and best=0 represents choosing no transaction. A singleton then performs no candidate evaluation.
Evaluate a sale using only earlier days
At each day≥1, compute candidate=prices[day]−minimum before updating minimum with today. This ordering makes the strict earlier-buy meaning explicit even though allowing a zero-profit same-day pair would not change the numeric optimum in this special task.
Discard dominated earlier buy prices
For any fixed future sale S, S−a≥S−b whenever a≤b. The cheaper buy is at least as good for every future sale, so no other earlier price needs to remain in state. This is a dominance proof, not a guess that the global minimum must be used.
Keep the global optimum separate from the buy minimum
After evaluating today’s candidate, update best, then lower minimum if today is cheaper. A newly low price is useful for later days, but it must not erase a profit already achieved by an earlier transaction.
State the exact numeric and output scope
Widen the sale price before subtraction. With nonnegative int prices, any profitable difference is at most 2147483647, so long is conservative and exact. The scalar result does not identify buy/sell days; a follow-up must carry indices and define ties explicitly.
Why it is correct
Prefix minimum invariant
Before processing day d, minimum is the least price among indices zero through d−1. It starts correctly at day one. Updating it after evaluating the sale incorporates precisely day d for the next iteration.
Best transaction ending today
Every legal transaction selling at day d buys at an earlier index. Replacing that buy by an earlier minimum-price day never decreases its profit and preserves chronology. candidate is therefore the greatest profit of a transaction selling today.
Global optimum with a no-trade option
Before day d, best is the maximum of zero and all profits selling before d. Maximizing with candidate includes every possible later endpoint exactly when processed. The final best covers every buy<sell pair and no trade. The increasing finite loop reads but never writes input.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Objects;
public final class Solution {
private Solution() {}
private static void validate(int[] prices) {
Objects.requireNonNull(prices, "prices");
if (prices.length > 100_000) throw new IllegalArgumentException("too many days");
for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price");
}
public static long maxProfit(int[] prices) {
validate(prices);
if (prices.length == 0) return 0;
int minimum = prices[0];
long best = 0;
for (int day = 1; day < prices.length; day++) {
long candidate = (long) prices[day] - minimum;
best = Math.max(best, candidate);
minimum = Math.min(minimum, prices[day]);
}
return best;
}
// Every legal chronological buy/sell pair; short inputs only.
public static long baseline(int[] prices) {
validate(prices);
long best = 0;
for (int buy = 0; buy < prices.length; buy++) {
for (int sell = buy + 1; sell < prices.length; sell++) {
best = Math.max(best, (long) prices[sell] - prices[buy]);
}
}
return best;
}
}
Read the meaningful blocks
Validate and handle no-price input
The separate full validation pass keeps the malformed-input policy consistent. No sentinel price is needed for empty input because it returns before accessing index zero.
Compute the candidate before lowering the minimum
This preserves the stronger invariant that the candidate buy is strictly earlier. It makes later index-returning extensions easier to reason about and avoids relying on a numeric coincidence.
Update independent summaries
best summarizes completed transactions; minimum summarizes future buying opportunities. They answer different questions and must not be reset together after a falling price.
Complexity
The validation and price scan take O(n) time, with O(1) auxiliary space and a scalar long output. Nonnegative int price bounds make each arithmetic operation fixed-width and exact.
The pair-enumeration baseline takes O(n²) time and O(1) space. A trace’s price and profit histories are explanatory snapshots rather than allocations in the reference. Returning transaction indices still needs only constant additional state.
Exact-state walkthroughs
Reveal normal and boundary traces
Preserve earlier profit while updating buying opportunities
Input: [7,1,5,3,6,4] · Maximum one-transaction profit: 5
Step 1 of 13: Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
Phase: initial.
Read-only daily prices
- day 0: 7
- day 1: 1
- day 2: 5
- day 3: 3
- day 4: 6
- day 5: 4
Current summary
- earlier/current prefix minimum: 7
- best completed profit: 0
No trade remains available at zero profit. Only one chronological buy/sell pair may contribute; separate positive swings cannot be added. A global minimum after a sale is not an eligible buy for that sale.
| Variable | Value |
|---|---|
| input | [7,1,5,3,6,4] |
| phase | "initial" |
| minimum | 7 |
| best | 0 |
| history | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] prices) { 6 Objects.requireNonNull(prices, "prices"); 7 if (prices.length > 100_000) throw new IllegalArgumentException("too many days"); 8 for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price"); 9 } 10 public static long maxProfit(int[] prices) { 11 validate(prices); 12 if (prices.length == 0) return 0; 13 int minimum = prices[0]; 14 long best = 0; 15 for (int day = 1; day < prices.length; day++) { 16 long candidate = (long) prices[day] - minimum; 17 best = Math.max(best, candidate); 18 minimum = Math.min(minimum, prices[day]); 19 } 20 return best; 21 } 22 // Every legal chronological buy/sell pair; short inputs only. 23 public static long baseline(int[] prices) { 24 validate(prices); 25 long best = 0; 26 for (int buy = 0; buy < prices.length; buy++) { 27 for (int sell = buy + 1; sell < prices.length; sell++) { 28 best = Math.max(best, (long) prices[sell] - prices[buy]); 29 } 30 } 31 return best; 32 } 33 } 34
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
- input
[7,1,5,3,6,4]- phase
"initial"- minimum
7- best
0- history
[]
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,1,5,3,6,4]- phase
"candidate"- minimum
7- best
0- history
[]- day
1- oldMinimum
7- candidate
-6
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,1,5,3,6,4]- phase
"commit"- minimum
1- best
0- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1}]- day
1- oldMinimum
7- candidate
-6
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,1,5,3,6,4]- phase
"candidate"- minimum
1- best
0- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1}]- day
2- oldMinimum
1- candidate
4
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,1,5,3,6,4]- phase
"commit"- minimum
1- best
4- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1}]- day
2- oldMinimum
1- candidate
4
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,1,5,3,6,4]- phase
"candidate"- minimum
1- best
4- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1}]- day
3- oldMinimum
1- candidate
2
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,1,5,3,6,4]- phase
"commit"- minimum
1- best
4- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":4,"minimum":1}]- day
3- oldMinimum
1- candidate
2
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,1,5,3,6,4]- phase
"candidate"- minimum
1- best
4- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":4,"minimum":1}]- day
4- oldMinimum
1- candidate
5
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,1,5,3,6,4]- phase
"commit"- minimum
1- best
5- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":4,"minimum":1},{"day":4,"oldMinimum":1,"candidate":5,"best":5,"minimum":1}]- day
4- oldMinimum
1- candidate
5
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,1,5,3,6,4]- phase
"candidate"- minimum
1- best
5- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":4,"minimum":1},{"day":4,"oldMinimum":1,"candidate":5,"best":5,"minimum":1}]- day
5- oldMinimum
1- candidate
3
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,1,5,3,6,4]- phase
"commit"- minimum
1- best
5- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":4,"minimum":1},{"day":4,"oldMinimum":1,"candidate":5,"best":5,"minimum":1},{"day":5,"oldMinimum":1,"candidate":3,"best":5,"minimum":1}]- day
5- oldMinimum
1- candidate
3
- Return the best legal profit or no trade.
best covers every legal selling endpoint processed, and zero remains available. The array is unchanged.
- input
[7,1,5,3,6,4]- phase
"complete"- minimum
1- best
5- history
[{"day":1,"oldMinimum":7,"candidate":-6,"best":0,"minimum":1},{"day":2,"oldMinimum":1,"candidate":4,"best":4,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":4,"minimum":1},{"day":4,"oldMinimum":1,"candidate":5,"best":5,"minimum":1},{"day":5,"oldMinimum":1,"candidate":3,"best":5,"minimum":1}]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
5
The global minimum occurs after the best sale
Input: [2,4,1] · Maximum one-transaction profit: 2
Step 1 of 7: Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
Phase: initial.
Read-only daily prices
- day 0: 2
- day 1: 4
- day 2: 1
Current summary
- earlier/current prefix minimum: 2
- best completed profit: 0
No trade remains available at zero profit. Only one chronological buy/sell pair may contribute; separate positive swings cannot be added. A global minimum after a sale is not an eligible buy for that sale.
| Variable | Value |
|---|---|
| input | [2,4,1] |
| phase | "initial" |
| minimum | 2 |
| best | 0 |
| history | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] prices) { 6 Objects.requireNonNull(prices, "prices"); 7 if (prices.length > 100_000) throw new IllegalArgumentException("too many days"); 8 for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price"); 9 } 10 public static long maxProfit(int[] prices) { 11 validate(prices); 12 if (prices.length == 0) return 0; 13 int minimum = prices[0]; 14 long best = 0; 15 for (int day = 1; day < prices.length; day++) { 16 long candidate = (long) prices[day] - minimum; 17 best = Math.max(best, candidate); 18 minimum = Math.min(minimum, prices[day]); 19 } 20 return best; 21 } 22 // Every legal chronological buy/sell pair; short inputs only. 23 public static long baseline(int[] prices) { 24 validate(prices); 25 long best = 0; 26 for (int buy = 0; buy < prices.length; buy++) { 27 for (int sell = buy + 1; sell < prices.length; sell++) { 28 best = Math.max(best, (long) prices[sell] - prices[buy]); 29 } 30 } 31 return best; 32 } 33 } 34
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
- input
[2,4,1]- phase
"initial"- minimum
2- best
0- history
[]
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[2,4,1]- phase
"candidate"- minimum
2- best
0- history
[]- day
1- oldMinimum
2- candidate
2
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[2,4,1]- phase
"commit"- minimum
2- best
2- history
[{"day":1,"oldMinimum":2,"candidate":2,"best":2,"minimum":2}]- day
1- oldMinimum
2- candidate
2
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[2,4,1]- phase
"candidate"- minimum
2- best
2- history
[{"day":1,"oldMinimum":2,"candidate":2,"best":2,"minimum":2}]- day
2- oldMinimum
2- candidate
-1
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[2,4,1]- phase
"commit"- minimum
1- best
2- history
[{"day":1,"oldMinimum":2,"candidate":2,"best":2,"minimum":2},{"day":2,"oldMinimum":2,"candidate":-1,"best":2,"minimum":1}]- day
2- oldMinimum
2- candidate
-1
- Return the best legal profit or no trade.
best covers every legal selling endpoint processed, and zero remains available. The array is unchanged.
- input
[2,4,1]- phase
"complete"- minimum
1- best
2- history
[{"day":1,"oldMinimum":2,"candidate":2,"best":2,"minimum":2},{"day":2,"oldMinimum":2,"candidate":-1,"best":2,"minimum":1}]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
2
Do not sum separate profitable swings
Input: [1,3,1,3] · Maximum one-transaction profit: 2
Step 1 of 9: Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
Phase: initial.
Read-only daily prices
- day 0: 1
- day 1: 3
- day 2: 1
- day 3: 3
Current summary
- earlier/current prefix minimum: 1
- best completed profit: 0
No trade remains available at zero profit. Only one chronological buy/sell pair may contribute; separate positive swings cannot be added. A global minimum after a sale is not an eligible buy for that sale.
| Variable | Value |
|---|---|
| input | [1,3,1,3] |
| phase | "initial" |
| minimum | 1 |
| best | 0 |
| history | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] prices) { 6 Objects.requireNonNull(prices, "prices"); 7 if (prices.length > 100_000) throw new IllegalArgumentException("too many days"); 8 for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price"); 9 } 10 public static long maxProfit(int[] prices) { 11 validate(prices); 12 if (prices.length == 0) return 0; 13 int minimum = prices[0]; 14 long best = 0; 15 for (int day = 1; day < prices.length; day++) { 16 long candidate = (long) prices[day] - minimum; 17 best = Math.max(best, candidate); 18 minimum = Math.min(minimum, prices[day]); 19 } 20 return best; 21 } 22 // Every legal chronological buy/sell pair; short inputs only. 23 public static long baseline(int[] prices) { 24 validate(prices); 25 long best = 0; 26 for (int buy = 0; buy < prices.length; buy++) { 27 for (int sell = buy + 1; sell < prices.length; sell++) { 28 best = Math.max(best, (long) prices[sell] - prices[buy]); 29 } 30 } 31 return best; 32 } 33 } 34
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
- input
[1,3,1,3]- phase
"initial"- minimum
1- best
0- history
[]
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[1,3,1,3]- phase
"candidate"- minimum
1- best
0- history
[]- day
1- oldMinimum
1- candidate
2
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[1,3,1,3]- phase
"commit"- minimum
1- best
2- history
[{"day":1,"oldMinimum":1,"candidate":2,"best":2,"minimum":1}]- day
1- oldMinimum
1- candidate
2
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[1,3,1,3]- phase
"candidate"- minimum
1- best
2- history
[{"day":1,"oldMinimum":1,"candidate":2,"best":2,"minimum":1}]- day
2- oldMinimum
1- candidate
0
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[1,3,1,3]- phase
"commit"- minimum
1- best
2- history
[{"day":1,"oldMinimum":1,"candidate":2,"best":2,"minimum":1},{"day":2,"oldMinimum":1,"candidate":0,"best":2,"minimum":1}]- day
2- oldMinimum
1- candidate
0
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[1,3,1,3]- phase
"candidate"- minimum
1- best
2- history
[{"day":1,"oldMinimum":1,"candidate":2,"best":2,"minimum":1},{"day":2,"oldMinimum":1,"candidate":0,"best":2,"minimum":1}]- day
3- oldMinimum
1- candidate
2
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[1,3,1,3]- phase
"commit"- minimum
1- best
2- history
[{"day":1,"oldMinimum":1,"candidate":2,"best":2,"minimum":1},{"day":2,"oldMinimum":1,"candidate":0,"best":2,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":2,"minimum":1}]- day
3- oldMinimum
1- candidate
2
- Return the best legal profit or no trade.
best covers every legal selling endpoint processed, and zero remains available. The array is unchanged.
- input
[1,3,1,3]- phase
"complete"- minimum
1- best
2- history
[{"day":1,"oldMinimum":1,"candidate":2,"best":2,"minimum":1},{"day":2,"oldMinimum":1,"candidate":0,"best":2,"minimum":1},{"day":3,"oldMinimum":1,"candidate":2,"best":2,"minimum":1}]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
2
No transaction beats a falling market
Input: [7,6,4] · Maximum one-transaction profit: 0
Step 1 of 7: Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
Phase: initial.
Read-only daily prices
- day 0: 7
- day 1: 6
- day 2: 4
Current summary
- earlier/current prefix minimum: 7
- best completed profit: 0
No trade remains available at zero profit. Only one chronological buy/sell pair may contribute; separate positive swings cannot be added. A global minimum after a sale is not an eligible buy for that sale.
| Variable | Value |
|---|---|
| input | [7,6,4] |
| phase | "initial" |
| minimum | 7 |
| best | 0 |
| history | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] prices) { 6 Objects.requireNonNull(prices, "prices"); 7 if (prices.length > 100_000) throw new IllegalArgumentException("too many days"); 8 for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price"); 9 } 10 public static long maxProfit(int[] prices) { 11 validate(prices); 12 if (prices.length == 0) return 0; 13 int minimum = prices[0]; 14 long best = 0; 15 for (int day = 1; day < prices.length; day++) { 16 long candidate = (long) prices[day] - minimum; 17 best = Math.max(best, candidate); 18 minimum = Math.min(minimum, prices[day]); 19 } 20 return best; 21 } 22 // Every legal chronological buy/sell pair; short inputs only. 23 public static long baseline(int[] prices) { 24 validate(prices); 25 long best = 0; 26 for (int buy = 0; buy < prices.length; buy++) { 27 for (int sell = buy + 1; sell < prices.length; sell++) { 28 best = Math.max(best, (long) prices[sell] - prices[buy]); 29 } 30 } 31 return best; 32 } 33 } 34
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
- input
[7,6,4]- phase
"initial"- minimum
7- best
0- history
[]
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,6,4]- phase
"candidate"- minimum
7- best
0- history
[]- day
1- oldMinimum
7- candidate
-1
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,6,4]- phase
"commit"- minimum
6- best
0- history
[{"day":1,"oldMinimum":7,"candidate":-1,"best":0,"minimum":6}]- day
1- oldMinimum
7- candidate
-1
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[7,6,4]- phase
"candidate"- minimum
6- best
0- history
[{"day":1,"oldMinimum":7,"candidate":-1,"best":0,"minimum":6}]- day
2- oldMinimum
6- candidate
-2
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[7,6,4]- phase
"commit"- minimum
4- best
0- history
[{"day":1,"oldMinimum":7,"candidate":-1,"best":0,"minimum":6},{"day":2,"oldMinimum":6,"candidate":-2,"best":0,"minimum":4}]- day
2- oldMinimum
6- candidate
-2
- Return the best legal profit or no trade.
best covers every legal selling endpoint processed, and zero remains available. The array is unchanged.
- input
[7,6,4]- phase
"complete"- minimum
4- best
0- history
[{"day":1,"oldMinimum":7,"candidate":-1,"best":0,"minimum":6},{"day":2,"oldMinimum":6,"candidate":-2,"best":0,"minimum":4}]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
0
No days
Input: [] · Maximum one-transaction profit: 0
Step 1 of 3: Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
Phase: initial.
Read-only daily prices
Empty.
Current summary
- earlier/current prefix minimum: no day
- best completed profit: 0
No trade remains available at zero profit. Only one chronological buy/sell pair may contribute; separate positive swings cannot be added. A global minimum after a sale is not an eligible buy for that sale.
| Variable | Value |
|---|---|
| input | [] |
| phase | "initial" |
| minimum | null |
| best | 0 |
| history | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] prices) { 6 Objects.requireNonNull(prices, "prices"); 7 if (prices.length > 100_000) throw new IllegalArgumentException("too many days"); 8 for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price"); 9 } 10 public static long maxProfit(int[] prices) { 11 validate(prices); 12 if (prices.length == 0) return 0; 13 int minimum = prices[0]; 14 long best = 0; 15 for (int day = 1; day < prices.length; day++) { 16 long candidate = (long) prices[day] - minimum; 17 best = Math.max(best, candidate); 18 minimum = Math.min(minimum, prices[day]); 19 } 20 return best; 21 } 22 // Every legal chronological buy/sell pair; short inputs only. 23 public static long baseline(int[] prices) { 24 validate(prices); 25 long best = 0; 26 for (int buy = 0; buy < prices.length; buy++) { 27 for (int sell = buy + 1; sell < prices.length; sell++) { 28 best = Math.max(best, (long) prices[sell] - prices[buy]); 29 } 30 } 31 return best; 32 } 33 } 34
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
- input
[]- phase
"initial"- minimum
null- best
0- history
[]
- Return the best legal profit or no trade.
best covers every legal selling endpoint processed, and zero remains available. The array is unchanged.
- input
[]- phase
"complete"- minimum
null- best
0- history
[]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
0
Full-width exact profit
Input: [0,2147483647] · Maximum one-transaction profit: 2147483647
Step 1 of 5: Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
Phase: initial.
Read-only daily prices
- day 0: 0
- day 1: 2147483647
Current summary
- earlier/current prefix minimum: 0
- best completed profit: 0
No trade remains available at zero profit. Only one chronological buy/sell pair may contribute; separate positive swings cannot be added. A global minimum after a sale is not an eligible buy for that sale.
| Variable | Value |
|---|---|
| input | [0,2147483647] |
| phase | "initial" |
| minimum | 0 |
| best | 0 |
| history | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] prices) { 6 Objects.requireNonNull(prices, "prices"); 7 if (prices.length > 100_000) throw new IllegalArgumentException("too many days"); 8 for (int price : prices) if (price < 0) throw new IllegalArgumentException("negative price"); 9 } 10 public static long maxProfit(int[] prices) { 11 validate(prices); 12 if (prices.length == 0) return 0; 13 int minimum = prices[0]; 14 long best = 0; 15 for (int day = 1; day < prices.length; day++) { 16 long candidate = (long) prices[day] - minimum; 17 best = Math.max(best, candidate); 18 minimum = Math.min(minimum, prices[day]); 19 } 20 return best; 21 } 22 // Every legal chronological buy/sell pair; short inputs only. 23 public static long baseline(int[] prices) { 24 validate(prices); 25 long best = 0; 26 for (int buy = 0; buy < prices.length; buy++) { 27 for (int sell = buy + 1; sell < prices.length; sell++) { 28 best = Math.max(best, (long) prices[sell] - prices[buy]); 29 } 30 } 31 return best; 32 } 33 } 34
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the first possible buy and a no-trade profit of zero.
A candidate sale must follow its buy strictly. Empty and singleton inputs return zero.
- input
[0,2147483647]- phase
"initial"- minimum
0- best
0- history
[]
- Price today’s sale against the cheapest strictly earlier buy.
Every more expensive earlier buy is dominated for this sale and every future sale. The global minimum could occur too late.
- input
[0,2147483647]- phase
"candidate"- minimum
0- best
0- history
[]- day
1- oldMinimum
0- candidate
2147483647
- Update completed profit, then future buying opportunities.
A new low price does not erase a previously completed profit. Separate profitable swings cannot be added under one-transaction semantics.
- input
[0,2147483647]- phase
"commit"- minimum
0- best
2147483647- history
[{"day":1,"oldMinimum":0,"candidate":2147483647,"best":2147483647,"minimum":0}]- day
1- oldMinimum
0- candidate
2147483647
- Return the best legal profit or no trade.
best covers every legal selling endpoint processed, and zero remains available. The array is unchanged.
- input
[0,2147483647]- phase
"complete"- minimum
0- best
2147483647- history
[{"day":1,"oldMinimum":0,"candidate":2147483647,"best":2147483647,"minimum":0}]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
2147483647
Test the contract
Input:
prices=[]
Output:0No possible transaction.
Input:
prices=[9]
Output:0No strictly later sale.
Input:
prices=[2,4,1]
Output:2Global min/max do not preserve chronology.
Input:
prices=[1,3,1,3]
Output:2Only one transaction.
Input:
prices=[0,2147483647]
Output:2147483647Exact extreme valid profit.
Input:
prices=[1,-1]
Output:IllegalArgumentExceptionNegative prices are rejected.
Common mistakes and counterexamples
Subtract the global minimum from the global maximum
Counterexample: [2,4,1] has a minimum after its maximum; three is not a legal profit.
For each sale use a strictly earlier prefix minimum.
Sum all positive daily increases
Counterexample: [1,3,1,3] has one-transaction profit two, not four.
Keep a single best sale-minus-earlier-buy difference.
Force a losing transaction
Counterexample: [7,6] should return zero, not −1.
Initialize best to zero because no trade is allowed.
Reset best when a new cheap price appears
Counterexample: [1,5,0] already achieved profit four before the final minimum.
Maintain the completed-profit maximum independently of future buy opportunities.
Follow-ups
Return buy and sell indices.
Remember the earliest index of the current minimum and a winning pair whenever profit improves. Define how to break equal-profit ties and how to represent no transaction. Compute the sale candidate before changing the minimum index.
Allow unlimited transactions.
Without fees or cooldowns, summing positive adjacent increases is optimal and can combine multiple swings. That is a different objective from one transaction; give its own decomposition proof rather than modifying this result informally.
Add fees, cooldowns, or a transaction budget.
The best earlier price alone may not encode whether a purchase is legal after earlier transactions. Derive holding/not-holding and budget/cooldown states with correct timing. This is a natural connection to the completed dynamic-programming lessons.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 111/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.