Best Time to Buy and Sell Stock with Transaction Fee

65.7k
0

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a time. A held share must be sold before another purchase.

Return the maximum total profit after subtracting fee exactly once for every completed buy-and-sell pair. Trading is optional, so the maximum profit can remain 0.

Example 1

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: Buying at 1 and selling at 8 earns 8 - 1 - 2 = 5. Buying at 4 and selling at 9 earns 9 - 4 - 2 = 3. The maximum total profit is 5 + 3 = 8.

Example 2

Input: prices = [9, 7, 5, 3], fee = 2
Output: 0
Explanation: Every later price is smaller, so every completed transaction loses money after the fee. Skipping all trades keeps the maximum profit at 0.

Recursion

Every day offers a small choice. An empty hand allows a purchase or a skip, while a held share allows a sale or a hold. A sale pays the transaction fee, so every completed trade receives exactly one fee deduction.

The same decision pattern continues on the next day, making recursion a natural fit. State solve(day, canBuy) stores the best profit from day onward. Value 1 for canBuy represents an empty hand, and value 0 represents a held share. The initial call starts at solve(0, 1) because day 0 begins without a purchased share.

Algorithm

  • Begin from solve(0, 1) because trading starts on the first day with an empty hand and permission to buy.

  • Stop with profit 0 after day n - 1 because no future sale or purchase remains available.

  • Compare buying with skipping whenever canBuy = 1 because an empty hand permits either opening a position or waiting.

  • Subtract the current price on a purchase because buying spends money and changes the next state to canBuy = 0.

  • Compare selling with holding whenever canBuy = 0 because an owned share permits either closing the position or waiting.

  • Add the current price and subtract fee on a sale because a completed transaction earns the sale value and pays exactly one fee.

  • Return the larger choice in every state because the strongest legal action preserves the maximum possible future profit.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the best profit from one trading state.
long long solve(
int day,
int canBuy,
vector<int>& prices,
int fee
) {
int n = prices.size();
// No trading opportunity remains after the last day.
if (day == n) {
return 0;
}
// An empty hand allows a purchase or a skip.
if (canBuy == 1) {
// Buying spends the current stock price.
long long buy = -prices[day]
+ solve(day + 1, 0, prices, fee);
// Skipping preserves permission to buy.
long long skip = solve(
day + 1, 1, prices, fee
);
// The stronger empty-hand choice is returned.
return max(buy, skip);
}
// Selling closes a trade and pays one fee.
long long sell = prices[day] - fee
+ solve(day + 1, 1, prices, fee);
// Holding preserves the owned-share state.
long long hold = solve(
day + 1, 0, prices, fee
);
// The stronger owned-share choice is returned.
return max(sell, hold);
}
public:
// Finds maximum profit with transaction fees.
long long maxProfit(vector<int>& prices, int fee) {
// Trading starts empty-handed on the first day.
return solve(0, 1, prices, fee);
}
};
// Driver code
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution obj;
cout << obj.maxProfit(prices, fee);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of days, because each day can branch into two choices across a recursion depth of N.

Space Complexity: O(N), because the recursion stack can contain up to one call for each day.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion reaches the same (day, canBuy) state through many earlier action sequences. Every repeated state has the same remaining prices, holding status, and fee, so every repeated calculation produces the same answer.

A dp table stores each completed state. A cached value returns immediately on later visits, while the purchase, sale, and skip transitions remain unchanged from recursion.

Algorithm

  • Begin with a dp table containing n rows and two columns, filled with -1 so every untouched state is clearly uncalculated.

  • Start from solve(0, 1) because the full trading period begins on day 0 without a held share.

  • Return 0 after the final day because no future action can add profit.

  • Reuse dp[day][canBuy] whenever a stored value exists because identical day and holding states have identical remaining choices.

  • Compare buying with skipping in an empty-hand state so the best opening decision enters the cache.

  • Compare selling after one fee with holding in an owned-share state so the best closing decision enters the cache.

  • Store and return the larger branch result because future visits can then avoid rebuilding the same decision tree.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds one state and caches the best profit.
long long solve(
int day,
int canBuy,
vector<int>& prices,
int fee,
vector<vector<long long>>& dp
) {
int n = prices.size();
// No trading opportunity remains after the last day.
if (day == n) {
return 0;
}
// A stored state avoids repeated trading paths.
if (dp[day][canBuy] != -1) {
return dp[day][canBuy];
}
long long bestProfit;
// An empty hand allows a purchase or a skip.
if (canBuy == 1) {
// Buying spends the current stock price.
long long buy = -prices[day]
+ solve(day + 1, 0, prices, fee, dp);
// Skipping preserves permission to buy.
long long skip = solve(
day + 1, 1, prices, fee, dp
);
// The stronger opening choice enters the cache.
bestProfit = max(buy, skip);
} else {
// Selling closes a trade and pays one fee.
long long sell = prices[day] - fee
+ solve(day + 1, 1, prices, fee, dp);
// Holding preserves the owned-share state.
long long hold = solve(
day + 1, 0, prices, fee, dp
);
// The stronger closing choice enters the cache.
bestProfit = max(sell, hold);
}
// Caching preserves the best result for reuse.
dp[day][canBuy] = bestProfit;
return dp[day][canBuy];
}
public:
// Finds maximum profit with cached states.
long long maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
// Minus one marks every uncalculated state.
vector<vector<long long>> dp(
n, vector<long long>(2, -1)
);
// Trading starts empty-handed on the first day.
return solve(0, 1, prices, fee, dp);
}
};
// Driver code
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution obj;
cout << obj.maxProfit(prices, fee);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because at most two states are solved once for each day.

Space Complexity: O(N), because the dp table stores two states for each of the N days, and the recursion stack can contain up to N calls.

Tabulation

Memoization still depends on recursive calls. A bottom-up dp table can store the same two states directly, starting from the known answer after the last day and moving backward toward day 0.

Row dp[day] depends only on row dp[day + 1], so reverse iteration guarantees every required future value is ready. Entry dp[0][1] remains the complete answer because trading begins on day 0 with permission to buy.

Algorithm

  • Begin with a dp table containing n + 1 rows and two columns, so row n can represent the period after all stock prices.

  • Keep both values in row n at 0 because no action after the final day can earn profit.

  • Move from day n - 1 toward day 0 so every transition can read the already-computed next-day states.

  • Set dp[day][1] to the larger value from buying or skipping because an empty hand allows either choice.

  • Set dp[day][0] to the larger value from selling after one fee or holding because a held share blocks another purchase.

  • Preserve the same purchase subtraction and fee-adjusted sale used by recursion so the state meaning never changes.

  • Return dp[0][1] because the full trading period starts on day 0 without a held share.

Dry Run

Best Time to Buy and Sell Stock with Transaction Fees Tabulation

Best Time to Buy and Sell Stock with Transaction Fees Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds maximum profit with bottom-up states.
long long maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
// Row n represents the period after all days.
vector<vector<long long>> dp(
n + 1, vector<long long>(2, 0)
);
// Reverse order makes next-day states available.
for (int day = n - 1; day >= 0; day--) {
// Buying or skipping starts from an empty hand.
long long buy = -prices[day]
+ dp[day + 1][0];
long long skip = dp[day + 1][1];
// The stronger empty-hand choice fills the state.
dp[day][1] = max(buy, skip);
// Selling after one fee closes the transaction.
long long sell = prices[day] - fee
+ dp[day + 1][1];
long long hold = dp[day + 1][0];
// The stronger owned-share choice fills the state.
dp[day][0] = max(sell, hold);
}
// The first day starts with permission to buy.
return dp[0][1];
}
};
// Driver code
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution obj;
cout << obj.maxProfit(prices, fee);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because two constant-time state transitions are calculated for each day.

Space Complexity: O(N), because the dp table stores two profit values for each of the N days, and no recursion stack is used.

Space Optimization

Each tabulation row reads only the next row. Older rows never enter another transition, so two next-day values and two current-day values can replace the full dp table.

Variables aheadCanBuy and aheadMustSell represent the next day. Both current values must be calculated before either ahead value changes, because both transitions depend on the same untouched next-day pair. The completed current pair then shifts forward for the following iteration.

Algorithm

  • Begin with aheadCanBuy = 0 and aheadMustSell = 0 because no profit remains after the last day in either state.

  • Move backward from day n - 1 so the retained ahead values always represent day day + 1.

  • Calculate currentCanBuy from buying or skipping so a purchase reads aheadMustSell and a skip reads aheadCanBuy.

  • Calculate currentMustSell from a fee-adjusted sale or holding so both legal owned-share choices are compared.

  • Finish both current calculations before shifting values because both states require the same unchanged next-day pair.

  • Shift currentCanBuy and currentMustSell into the ahead variables so the next iteration receives the newly completed row.

  • Return aheadCanBuy after day 0 because trading begins with an empty hand and permission to buy.

Dry Run

Best Time to Buy and Sell Stock with Transaction Fees Space Optimization

Best Time to Buy and Sell Stock with Transaction Fees Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds maximum profit with rolling states.
long long maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
// Both states earn zero after the final day.
long long aheadCanBuy = 0;
long long aheadMustSell = 0;
// Reverse order keeps the next-day pair available.
for (int day = n - 1; day >= 0; day--) {
// The current buy state compares both choices.
long long currentCanBuy = max(
-prices[day] + aheadMustSell,
aheadCanBuy
);
// A sale closes a trade and pays one fee.
long long currentMustSell = max(
prices[day] - fee + aheadCanBuy,
aheadMustSell
);
// Shift both current values into the ahead pair.
aheadCanBuy = currentCanBuy;
aheadMustSell = currentMustSell;
}
// The first day starts with permission to buy.
return aheadCanBuy;
}
};
// Driver code
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution obj;
cout << obj.maxProfit(prices, fee);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because two constant-time state transitions are calculated for each day.

Space Complexity: O(1), because four profit variables store the required states, replacing the full dp table, and no recursion stack is used.

Interview follow-up Questions

No. A completed buy-and-sell pair pays fee exactly once. The presented transitions subtract the fee during selling.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Input: k = 2, prices = [5, 2, 4, 0, 3, 7] Output: 9 Explanation: Buying at 2 and selling at 4 earns 2 . Buying at 0 and selling at 7 earns 7 , producing total profit 9 . Input: k = 3, prices = [8,...

50.8k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0