Stop Memorizing Stock Problems - A Single DP Template for All Buy/Sell Variants (+Bonus Problem!!)
488
All Stock Buy/Sell problems are the same DP state machine - only the constraints change
- i/p: price[day]
- can buy/sell/rest on any day
- B then S only then B again. BBSS not allowed. BSBS is fine
- can be bought even on 0th day w/o funds cuz we r finding maxProfit anyways
- aim: generate max Profit (after selling) given at most 1,2,3..../k/infinity allowed transactions
- Initially
- profitWithoutStock = 0 --> no sells before market opening day => no profits
- profitWithStock = -(int)1e9 --> since we maximise profit and it's impossible to hold/buy stock before market opening day, we initialise with most min possible to prevent it from being considered as maxProfit
121. Best Time to Buy and Sell Stock - only 1 transaction allowed
int maxProfit(int[] prices) {
int profitWithoutStock = 0; // without => sell today if have it
int profitWithStock = Integer.MIN_VALUE; // with => either keep or buy today
for (int price: prices) {
profitWithStock = Math.max(
profitWithStock, // rest today ... profitWithStock on prev day
// profitWithoutStock-price // wrong cuz no "previous profit" to carry into buying cuz only 1 transaction allowed
-price // buy today - buying reduces treasury
);
// profitWithoutStock on current day either could be profitWithoutStock on prev day or....
profitWithoutStock = Math.max(
profitWithoutStock, // rest today
profitWithStock + price // sell today
);
}
return profitWithoutStock; // i.e profit on selling
}122. Best Time to Buy and Sell Stock II - infinite transactions => profit reuse allowed
Allowing same-day SELL → BUY means the cash from the sell is immediately reusable, even though buying and selling at the same price yields zero net profit
public int maxProfit(int[] prices) {
int profitWithoutStock = 0;
int profitWithStock = Integer.MIN_VALUE;
for (int price: prices) {
profitWithStock = Math.max(
profitWithStock,
profitWithoutStock - price // 121 forbids reusing profit for buying again; 122 allows it
);
profitWithoutStock = Math.max(
profitWithoutStock,
profitWithStock + price
);
}
return profitWithoutStock;
}123. Best Time to Buy and Sell Stock III - at most 2 transactions allowed
public int maxProfit(int[] prices) {
int k = 2;
int[] profitWithoutStock = new int[k + 1]; // profitWithoutStock[t] → best profit after t completed sells, and not holding stock
int[] profitWithStock = new int[k + 1];
Arrays.fill(profitWithStock, Integer.MIN_VALUE);
for (int price: prices) {
// When processing today’s price: must read from left (t-1) and must write to right (t). So fill right → left to avoid overwriting the source (just like Coin Change Combination (Single))
for (int t = k; t >= 1; t--) {
profitWithStock[t] = Math.max( // profitWithStock -> buying
profitWithStock[t],
profitWithoutStock[t - 1] - price // buying is start of a new transaction (t), so prev corresponds to the older transaction (t-1)
);
profitWithoutStock[t] = Math.max( // profitWithoutStock -> selling
profitWithoutStock[t],
profitWithStock[t] + price // selling is end of a transaction, so prev corresponds to the same transaction
);
}
}
return profitWithoutStock[k];
}188. Best Time to Buy and Sell Stock IV - at most k transactions allowed
public int maxProfit(int k, int[] prices) {
int[] profitWithoutStock = new int[k + 1];
int[] profitWithStock = new int[k + 1];
Arrays.fill(profitWithStock, Integer.MIN_VALUE);
for (int price: prices) {
for (int t = k; t >= 1; t--) {
profitWithStock[t] = Math.max(
profitWithStock[t],
profitWithoutStock[t - 1] - price
);
profitWithoutStock[t] = Math.max(
profitWithoutStock[t],
profitWithStock[t] + price
);
}
}
return profitWithoutStock[k];
}714. Best Time to Buy and Sell Stock with Transaction Fee
The transaction fee is only charged once for each stock purchase and sale
public int maxProfit(int[] prices, int fee) {
int profitWithoutStock = 0;
int profitWithStock = Integer.MIN_VALUE;
for (int price: prices) {
// Update the buy/hold state first so today's sell cannot fund today's buy (fee-sensitive)
profitWithStock = Math.max(
profitWithStock,
// profitWithoutStock - price - fee
profitWithoutStock - price
);
profitWithoutStock = Math.max(
profitWithoutStock,
// profitWithStock + price
profitWithStock + price - fee
);
}
return profitWithoutStock;
}309. Best Time to Buy and Sell Stock with Cooldown - 1 day cooldown
public int maxProfit(int[] prices) {
int profitWithoutStock = 0;
int profitWithStock = Integer.MIN_VALUE;
int profitWithoutStockTwoDaysAgo = 0;
for (int price: prices) {
int prevProfitWithoutStock = profitWithoutStock;
profitWithStock = Math.max(
profitWithStock,
profitWithoutStockTwoDaysAgo - price
);
profitWithoutStock = Math.max( // after this update prevProfitWithoutStock becomes profitWithoutStockTwoDaysAgo
profitWithoutStock,
profitWithStock + price
);
profitWithoutStockTwoDaysAgo = prevProfitWithoutStock;
}
return profitWithoutStock;
}Q. Best Time to Buy and Sell Stock with Cooldown - k day cooldown
public int maxProfit(int[] prices, int k) {
int profitWithoutStock = 0;
int profitWithStock = Integer.MIN_VALUE;
Deque < Integer > history = new ArrayDeque < > ();
// profitWithoutStock before day 0 is 0
for (int i = 0; i <= k; i++) { // Initialize sliding window of size (k + 1)
history.addLast(0);
}
for (int price: prices) {
history.pollFirst(); // since window size is fixed, so before adding in window have to remove first
history.addLast(profitWithoutStock); // before updating profitWithoutStock have to add it in history
int allowedBuyBase = history.peekFirst(); // above 2 lines shifted the window from [i-k-1, i-1] to [i-k, i]. So to get (i-k-1) need to peek again even after initial poll
profitWithStock = Math.max(
profitWithStock,
allowedBuyBase - price
);
profitWithoutStock = Math.max(
profitWithoutStock,
profitWithStock + price
);
}
return profitWithoutStock;
}Comments (1)