Definition
- Single transaction – track the lowest price seen so far (best buy point) and the best profit of selling today at that minimum. One pass, O(1) space.
- Unlimited transactions – sum every positive difference between consecutive days; each gain represents a profitable buy-sell pair. One pass, O(1) space.
- Running minimum – guarantees the buy day always precedes the sell day without comparing every pair.
- Greedy insight – capturing every positive daily step is equivalent to buying at each local trough and selling at each local peak.
The National Bank of India trading desk reviews a security's daily prices and wants the maximum profit: either from one clean buy-and-sell, or from many back-to-back trades capturing every rise.
Understanding the Concepts
What is the Best Time to Buy and Sell Stock problem?
Given an array of daily prices, find the maximum profit from buying and selling a stock. The single-transaction variant allows one buy and one sell. The unlimited-transaction variant allows as many trades as you want (but you must sell before buying again).
At the National Bank of India, the trading desk computes maximum achievable profit on a security's price series under different trading rules.
package com.bank.trading;
public class StockProfitDemo {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println("Single: " + maxProfitSingle(prices));
System.out.println("Unlimited: " + maxProfitUnlimited(prices));
}
// implementations below
}
How does the single-transaction solution work?
Scan the prices while tracking the minimum price seen so far. On each day, compute the profit of selling at today's price minus the running minimum. Keep the best such profit. Because the minimum only looks backward, the buy day is always before the sell day.
package com.bank.trading;
public class SingleTransaction {
static int maxProfitSingle(int[] prices) {
int minSoFar = prices[0];
int bestProfit = 0;
for (int price : prices) {
minSoFar = Math.min(minSoFar, price);
bestProfit = Math.max(bestProfit, price - minSoFar);
}
return bestProfit;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println("Max profit (1 trade): " + maxProfitSingle(prices));
// Buy at 1, sell at 6 -> profit = 5
}
}
Max profit (1 trade): 5
How does the unlimited-transaction solution work?
The maximum profit with unlimited transactions is the sum of every positive day-over-day difference. Each positive step represents buying at yesterday's price and selling at today's price. Capturing every upward move is mathematically equivalent to buying at every local trough and selling at every local peak.
package com.bank.trading;
public class UnlimitedTransactions {
static int maxProfitUnlimited(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println("Max profit (unlimited): " + maxProfitUnlimited(prices));
// Day 1->2: +4, Day 3->4: +3 -> total = 7
}
}
Max profit (unlimited): 7
How does the running minimum work step by step?
- For prices [7, 1, 5, 3, 6, 4]:
- Day 0: price=7, min=7, profit=0
- Day 1: price=1, min=1, profit=0
- Day 2: price=5, min=1, profit=4
- Day 3: price=3, min=1, profit=4 (3-1=2, less than 4)
- Day 4: price=6, min=1, profit=5
- Day 5: price=4, min=1, profit=5 (4-1=3, less than 5)
package com.bank.trading;
public class RunningMinTrace {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int min = prices[0], best = 0;
for (int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
best = Math.max(best, prices[i] - min);
System.out.println("Day " + i + ": price=" + prices[i]
+ " min=" + min + " best=" + best);
}
}
}
Day 0: price=7 min=7 best=0
Day 1: price=1 min=1 best=0
Day 2: price=5 min=1 best=4
Day 3: price=3 min=1 best=4
Day 4: price=6 min=1 best=5
Day 5: price=4 min=1 best=5
Why is summing positive gains optimal for unlimited trades?
Every upward price movement is a profit opportunity. Summing all positive daily differences captures every rise without missing any. This is equivalent to buying at every local minimum and selling at every local maximum, but simpler to implement.
Prices: 7 1 5 3 6 4
Diffs: -6 +4 -2 +3 -2
Positive: +4 +3
Total: 4 + 3 = 7
Equivalent trades:
Buy at 1, sell at 5 -> +4
Buy at 3, sell at 6 -> +3
Total: 7
How do the two approaches compare?
| Variant | Algorithm | Time | Space |
|---------|-----------|------|-------|
| Single transaction | Running minimum | O(n) | O(1) |
| Unlimited transactions | Sum positive diffs | O(n) | O(1) |
| At most K transactions | State-machine DP | O(n*K) | O(K) |
| With cooldown | State-machine DP | O(n) | O(1) |
What are the edge cases?
Edge cases include constantly decreasing prices (profit = 0), constant prices (profit = 0), and a single day (no trade possible, profit = 0).
package com.bank.trading;
public class StockEdgeCases {
public static void main(String[] args) {
// Always decreasing
System.out.println(maxProfitSingle(new int[]{5, 4, 3, 2, 1})); // 0
// Constant
System.out.println(maxProfitSingle(new int[]{3, 3, 3})); // 0
// Single day
System.out.println(maxProfitSingle(new int[]{5})); // 0
// Two days, profitable
System.out.println(maxProfitSingle(new int[]{1, 5})); // 4
}
static int maxProfitSingle(int[] prices) {
if (prices.length < 2) return 0;
int min = prices[0], best = 0;
for (int p : prices) { min = Math.min(min, p); best = Math.max(best, p - min); }
return best;
}
}
0
0
0
4
What about the K-transaction and cooldown variants?
The K-transaction variant uses a state-machine DP tracking holding and not-holding states for up to K transactions. The cooldown variant adds a state for resting after a sell. These are harder but build on the same foundation.
package com.bank.trading;
public class KTransactions {
// At most K transactions
static int maxProfitK(int k, int[] prices) {
if (prices.length < 2 || k == 0) return 0;
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
java.util.Arrays.fill(buy, Integer.MIN_VALUE);
for (int price : prices) {
for (int t = 1; t <= k; t++) {
buy[t] = Math.max(buy[t], sell[t - 1] - price);
sell[t] = Math.max(sell[t], buy[t] + price);
}
}
return sell[k];
}
public static void main(String[] args) {
int[] prices = {3, 2, 6, 5, 0, 3};
System.out.println("K=2: " + maxProfitK(2, prices)); // 7
}
}
K=2: 7
What should a senior engineer know?
- Problem family. Best Time to Buy and Sell Stock has 6 variants (I through VI on LeetCode). The single and unlimited cases are greedy; the rest use DP.
- State machine. The K-transaction DP tracks states: not holding, holding, resting. Each state transitions based on buy, sell, or rest actions.
- BigDecimal for real trading. In production, prices and profits are
BigDecimalto avoid floating-point rounding on fractional prices. - No time travel. The running minimum ensures you never sell before you buy. This is the fundamental correctness property.
// Production: use BigDecimal for prices
import java.math.BigDecimal;
BigDecimal min = prices[0];
BigDecimal best = BigDecimal.ZERO;
for (BigDecimal p : prices) {
if (p.compareTo(min) < 0) min = p;
BigDecimal profit = p.subtract(min);
if (profit.compareTo(best) > 0) best = profit;
}
Visual Overview
Single Transaction: Prices: 7 1 5 3 6 4 Min: 7 1 1 1 1 1 Profit: 0 0 4 2 5 3 Best: 0 0 4 4 5 5 -> answer: 5 Unlimited Transactions: Prices: 7 1 5 3 6 4 Diffs: -6 +4 -2 +3 -2 Sum positives: 4 + 3 = 7 -> answer: 7 ┌────────────────────────────────────────────┐ │ Single: buy at day 1 (1), sell day 4 (6) │ │ Unlimited: buy 1 sell 5 (+4), buy 3 sell 6 (+3) │ └────────────────────────────────────────────┘
Key Takeaway
Best Time to Buy and Sell Stock is a family of problems, and the two base cases are both greedy single passes. For a single transaction, I track the lowest price seen so far and compute the profit of selling at each day's price against that minimum, keeping the best. The running minimum guarantees the buy day is always before the sell day.
For unlimited transactions, the maximum profit is the sum of every positive day-over-day difference. Capturing each upward step is mathematically equivalent to buying at every local trough and selling at every local peak. Both algorithms are O(n) time and O(1) space with no table at all.
The harder variants, limiting to at most K transactions or adding a cooldown day, require state-machine dynamic programming that tracks holding and not-holding states. These build on the same intuition but need a proper DP table.
At the National Bank of India, the trading desk used the running-minimum scan for the single-trade figure and the positive-gain sum for the unlimited figure, both fast enough for real-time dashboards over daily price series.
Remember one sentence: for one trade track the running minimum and best sell; for unlimited trades sum every positive daily gain; both are O(n) greedy passes.
---