Dynamic Programming for Optimal Stock Trading: Comparing Hindsight-Based Optimization with Real-Time Predictive Models
The "Best Time to Buy and Sell Stock" problem is a staple of LeetCode and coding interviews. Its classic dynamic programming solution finds the perfect trades, but only because it already knows every future price.
Real traders never have that advantage. This post compares the perfect-hindsight solution with a realistic machine learning model, and introduces a simple way to measure the difference between them: the regret gap.
Quick Summary
Dynamic programming (DP) finds the maximum possible profit, but it assumes you know all future prices.
Real trading is different: decisions are made with only past data.
A machine learning model (logistic regression) can make realistic, day-by-day trading decisions.
The regret gap = the profit a realistic model misses compared with the perfect DP result.
The regret gap gives context: a $5,000 profit means very different things if the maximum was $5,500 or $50,000.
The Problem: When to Buy and When to Sell
You get a list of stock prices, one per day. The goal is to pick the buy and sell days that give the highest profit.
Take this six-day example:
Day | 1 | 2 | 3 | 4 | 5 | 6 |
Price | 7 | 1 | 5 | 3 | 6 | 4 |
The answer depends on the rules:
One transaction allowed: buy at 1, sell at 6. Profit = 5.
Multiple transactions allowed: buy at 1, sell at 5 (profit 4), then buy at 3, sell at 6 (profit 3). Total profit = 7.
Harder versions add transaction fees, cooldown periods after selling, or a cap on the number of trades. Checking every possible combination of days works for six prices, but breaks down with thousands or millions. That is where dynamic programming comes in.
How Dynamic Programming Solves It
Dynamic programming breaks a big problem into smaller related problems. It stores each result once and reuses it, instead of recalculating it again and again.
A problem suits DP when it has two properties:
Optimal substructure: the best overall answer is built from the best answers to smaller parts.
Overlapping subproblems: the same smaller problems come up repeatedly.
Two states, updated every day
For each day, the algorithm tracks the best possible position in two situations:
Not holding a stock: either stay in cash, or sell the stock held so far.
Holding a stock: either keep holding, or buy today.
It always keeps the better option in each state. By the last day, the "not holding" state holds the maximum profit.
Walking through the example
Day 1 (price 7): nothing useful yet.
Day 2 (price 1): buying at 1 beats buying at 7.
Day 3 (price 5): selling gives a profit of 4.
Day 4 (price 3): multiple trades are allowed, so buy again.
Day 5 (price 6): selling adds a profit of 3.
Result: maximum profit = 7.
The key advantage: DP never tests every sequence of trades separately. It makes one pass through the prices, updating the two best positions as it goes.
The Catch: Perfect Hindsight
The DP algorithm gets the complete price list before it starts. In effect, it knows the future.
When it looks at the price of 1, it already knows the price will rise to 5. A real trader at that moment does not. The price could rise, stay flat, or fall further.
So DP is not a trading strategy. It is a benchmark that answers one question: what is the maximum profit possible if all future prices were known?
Computer scientists call this the difference between offline and online algorithms (Borodin & El-Yaniv, 1998):
Offline algorithm | Online algorithm | |
Data available | Entire input, upfront | Arrives one step at a time |
Knows the future? | Yes | No |
Example here | DP with full price list | A real trader or trading bot |
Real-world stock trading is an online problem.
Building a Realistic Model
A realistic algorithm can only use information available at the time of each decision. Machine learning fits this well: it studies past data and estimates whether the price is likely to go up or down.
What the model looks at
Previous prices and daily returns
Moving averages (for example, 5-day and 10-day)
Trading volume
Market volatility
Momentum indicators
If the model predicts a rise, the algorithm buys or keeps holding. If it predicts a fall, the algorithm sells or stays in cash. Either way, it is an estimate, not knowledge.
Why logistic regression
Despite its name, logistic regression is a classification method. Here it sorts each day into one of two outcomes:
The price will rise tomorrow.
The price will not rise tomorrow.
The model learns patterns from past data, then is tested on data it has never seen.
Avoid look-ahead bias
Training and test data must stay in chronological order. For example, train on the first 70% of the data and test on the most recent 30%.
Never split the data randomly. Mixing past and future rows lets future information leak into training, which makes results look far better than they really are.
The Regret Gap
The regret gap is the profit a realistic model misses compared with the perfect-hindsight result.
Regret Gap = DP Profit - Model Profit
Worked example
Measure | Value |
DP maximum profit (perfect hindsight) | $10,000 |
Predictive model profit | $6,500 |
Regret gap | $3,500 |
Regret gap as % of maximum | 35% |
Share of maximum captured | 65% |
The idea comes from online learning research, where regret measures how far an actual algorithm falls short of an ideal benchmark (Cesa-Bianchi & Lugosi, 2006).
Why it matters
A profit figure alone says little. Suppose Algorithm A makes $5,000:
If the maximum possible was $5,500, Algorithm A did extremely well.
If the maximum possible was $50,000, the same result is weak.
The regret gap supplies that missing context.
Practical Applications
A fair benchmark. Instead of asking only "did the model make money?", researchers can ask how close it came to the best possible result.
A bridge from coding to FinTech. Students can start with a familiar LeetCode problem and grow it into a real research project covering DP, machine learning, data analysis and online decision-making.
Comparing models. Swap logistic regression for decision trees, random forests, support vector machines, neural networks or reinforcement learning. The model with the smallest regret gap wins.
Testing the efficient market hypothesis. The hypothesis says prices quickly absorb all available information, making consistent prediction very hard (Fama, 1970). Persistently large regret gaps would support that view.
Accuracy is not profit. A model can predict many small rises correctly, then miss one big crash. Judge trading models on total return, maximum drawdown, risk-adjusted return, transaction costs and the regret gap, not accuracy alone.
Market conditions. Calculate the regret gap separately for rising, falling and highly volatile markets to see where predictive models do best.
Conclusion
Dynamic programming calculates the maximum possible trading profit efficiently, by tracking the best position when holding and when not holding a stock. But it assumes every future price is known, which no real trader can claim.
A machine learning model is more realistic because it decides using only past information. The regret gap measures how close that realistic model gets to the perfect benchmark.
Future work could add transaction costs, multiple stocks, portfolio optimisation, deep learning and reinforcement learning, and test the regret gap across different markets and economic conditions.
The real question is not "What is the maximum profit possible?" It is:
How close can an algorithm that does not know the future get to one that does?
Appendix: Python Implementation
A simplified version of the experiment, in six steps:
Collect historical stock price data.
Use DP to calculate the maximum profit with perfect hindsight.
Create historical features for the ML model.
Split the data chronologically into training and test sets.
Train logistic regression to predict whether the price rises the next day.
Compare the model's profit with the DP result.
A more advanced study could add transaction fees, bid-ask spreads, market slippage and further measures of financial performance.
References
Borodin, A., & El-Yaniv, R. (1998). Online computation and competitive analysis. Cambridge University Press.
Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press.
Fama, E. F. (1970). Efficient capital markets: A review of theory and empirical work. The Journal of Finance, 25(2), 383-417. https://doi.org/10.2307/2325486
Markowitz, H. (1952). Portfolio selection. The Journal of Finance, 7(1), 77-91. https://doi.org/10.2307/2975974
Murphy, K. P. (2022). Probabilistic machine learning: An introduction. MIT Press.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press.
VanderPlas, J. (2016). Python data science handbook: Essential tools for working with data. O'Reilly Media.
