Best Time to Buy and Sell Stock III: At Most Two Transactions

119.5k
0

An integer array prices is given, where prices[index] represents the stock price on day index.

At most two transactions may be completed. Every transaction contains one purchase followed by one sale, and a new purchase is allowed only after the previous stock has been sold. Return the maximum total profit. Skipping every transaction is allowed.

Example 1

Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output: 6
Explanation: Buying at 0 and selling at 3 gives profit 3. A later purchase at 1 and sale at 4 gives another profit 3, producing total profit 6.

Example 2

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Every later price is lower, so skipping all transactions preserves the maximum profit of 0.

Recursion

Each day offers a small set of choices. When no stock is held, we can buy at the current price or skip the day. When a stock is held, we can sell at the current price or keep holding. Every choice moves to the next day, so the same decision pattern is repeated on a smaller suffix of the price array.

The state solve(index, canBuy, remainingTransactions) represents the maximum profit possible from day index onward. The flag canBuy tells us whether we are allowed to buy, while remainingTransactions counts how many completed transactions can still be made. The initial state (0, 1, 2) starts from day 0 with no stock held and the full limit of two transactions available.

Algorithm

  • Start with solve(0, 1, 2) because trading begins on day 0 with no stock held and both transactions available.

  • Return 0 when all days are processed or remainingTransactions == 0 because no further completed transaction can be made.

  • When canBuy == 1, explore buying and skipping the current day, subtracting the current price only for the buy branch because purchasing costs money.

  • When canBuy == 0, explore selling and holding the current stock, adding the current price only for the sell branch because selling generates profit.

  • Decrease remainingTransactions after a sale because one complete buy-sell transaction has been finished.

  • Keep the maximum of the available choices at every state because we want the highest possible profit.

  • Return the result of solve(0, 1, 2) because this state represents the complete price array with the full transaction limit available.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best profit from one trading state.
int solve(
int index,
int canBuy,
int remainingTransactions,
vector<int>& prices
) {
int n = prices.size();
// No earning action remains after either limit ends.
if (index == n || remainingTransactions == 0) {
return 0;
}
// An empty portfolio allows buying or waiting.
if (canBuy == 1) {
// Buying opens a position and spends today's price.
int buy = -prices[index] + solve(
index + 1, 0, remainingTransactions, prices
);
// Waiting keeps the full transaction limit available.
int skip = solve(
index + 1, 1, remainingTransactions, prices
);
// The more profitable empty-portfolio choice is kept.
return max(buy, skip);
}
// Selling closes a position and completes one trade.
int sell = prices[index] + solve(
index + 1, 1, remainingTransactions - 1, prices
);
// Holding preserves the open position for a later price.
int hold = solve(
index + 1, 0, remainingTransactions, prices
);
// The more profitable held-stock choice is kept.
return max(sell, hold);
}
public:
// Returns the largest profit from at most two trades.
int maxProfit(vector<int>& prices) {
// Trading starts empty with both sales available.
return solve(0, 1, 2, prices);
}
};
// Driver code
int main() {
vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of days, because each day can generate two recursive branches, producing an exponential number of calls over a maximum depth of N.

Space Complexity: O(N), where N is the number of days, because the recursion stack can contain at most 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 can reach the same combination of day, ownership state, and remaining transactions through different trading histories. Recomputing the same state repeatedly adds unnecessary work because its answer does not depend on how that state was reached.

A three-dimensional dp array stores the result of every calculated state. The recursive choices remain unchanged; the only difference is that a previously solved state returns its cached value immediately instead of exploring the same subtree again.

Algorithm

  • Create dp[index][canBuy][remainingTransactions] with every value initialized to -1 so each uncalculated trading state has a clear marker.

  • Start with solve(0, 1, 2) because trading begins on day 0 with no stock held and two transactions available.

  • Return 0 when the end of the price array is reached or remainingTransactions == 0 because no further completed transaction is possible.

  • Return the stored dp[index][canBuy][remainingTransactions] when it is already calculated so repeated states avoid another recursive expansion.

  • When canBuy == 1, evaluate the buy and skip choices because no stock is currently held.

  • When canBuy == 0, evaluate the sell and hold choices because a stock is currently held.

  • Decrease remainingTransactions only in the sell branch because a transaction is completed only after a stock is sold.

  • Store the maximum legal choice in dp[index][canBuy][remainingTransactions] so future visits can reuse the best result.

  • Return dp[0][1][2] because this state represents the complete trading problem with the full transaction limit.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns a cached profit for one trading state.
int solve(
int index,
int canBuy,
int remainingTransactions,
vector<int>& prices,
vector<vector<vector<int>>>& dp
) {
int n = prices.size();
// No earning action remains after either limit ends.
if (index == n || remainingTransactions == 0) {
return 0;
}
// A calculated state can be reused without branching.
if (dp[index][canBuy][remainingTransactions] != -1) {
return dp[index][canBuy][remainingTransactions];
}
// An empty portfolio allows buying or waiting.
if (canBuy == 1) {
// Buying opens a position and spends today's price.
int buy = -prices[index] + solve(
index + 1,
0,
remainingTransactions,
prices,
dp
);
// Waiting keeps the full transaction limit available.
int skip = solve(
index + 1,
1,
remainingTransactions,
prices,
dp
);
// Cache storage prevents later recalculation.
dp[index][canBuy][remainingTransactions] = max(
buy, skip
);
return dp[index][canBuy][remainingTransactions];
}
// Selling closes a position and completes one trade.
int sell = prices[index] + solve(
index + 1,
1,
remainingTransactions - 1,
prices,
dp
);
// Holding preserves the open position for a later price.
int hold = solve(
index + 1,
0,
remainingTransactions,
prices,
dp
);
// Cache storage prevents later recalculation.
dp[index][canBuy][remainingTransactions] = max(
sell, hold
);
return dp[index][canBuy][remainingTransactions];
}
public:
// Returns the largest profit from at most two trades.
int maxProfit(vector<int>& prices) {
int n = prices.size();
// Sentinel values mark every state as uncalculated.
vector<vector<vector<int>>> dp(
n,
vector<vector<int>>(2, vector<int>(3, -1))
);
// Trading starts empty with both sales available.
return solve(0, 1, 2, prices, dp);
}
};
// Driver code
int main() {
vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because there are N × 2 × 3 reachable states, and each state is calculated once with constant-time transition work.

Space Complexity: O(N), where N is the number of days, because the dp array stores N × 2 × 3 values and the recursion stack can hold at most O(N) calls.

Tabulation

Memoization still depends on recursive calls and stack frames. Tabulation writes the same states into a dp array from the last day toward the first day, removing recursion while preserving every transition.

Every state at day index depends only on day index + 1. Processing days backward guarantees the required next-day answers are already available. Row n stores zero profit because no trading day remains.

Algorithm

  • Build dp with n + 1 day rows, two ownership states, and three transaction counts so every recursive state has an iterative position.

  • Leave row n and every zero-transaction state at 0 because no future action can earn profit from either boundary.

  • Move from day n - 1 down to day 0 because each current transition reads answers from the already calculated next day.

  • Calculate the empty-portfolio state from buying and waiting because subtracting the current price correctly records the cost of opening a position.

  • Calculate the held-stock state from selling and holding, adding the price and reducing the count only for the selling choice.

  • Store the larger legal choice for both ownership states because optional trading must preserve the best future profit.

  • Return dp[0][1][2] because day 0, permission to buy, and two remaining sales form the complete starting state.

Dry Run

best-time-to-buy-and-sell-stock-iii-tabulation-state-key-fixed.png

best-time-to-buy-and-sell-stock-iii-tabulation-state-key-fixed.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the largest profit from at most two trades.
int maxProfit(vector<int>& prices) {
int n = prices.size();
// The extra row represents the exhausted day range.
vector<vector<vector<int>>> dp(
n + 1,
vector<vector<int>>(2, vector<int>(3, 0))
);
// Backward order makes next-day answers available.
for (int index = n - 1; index >= 0; index--) {
// Zero remaining trades stays at the base value.
for (
int remainingTransactions = 1;
remainingTransactions <= 2;
remainingTransactions++
) {
// Buying spends money before a later sale.
int buy = -prices[index]
+ dp[index + 1][0][remainingTransactions];
// Waiting preserves an empty portfolio.
int skip = dp[index + 1][1]
[remainingTransactions];
// The best empty-portfolio transition is stored.
dp[index][1][remainingTransactions] = max(
buy, skip
);
// Selling earns money and completes one trade.
int sell = prices[index]
+ dp[index + 1][1]
[remainingTransactions - 1];
// Holding preserves the open position.
int hold = dp[index + 1][0]
[remainingTransactions];
// The best held-stock transition is stored.
dp[index][0][remainingTransactions] = max(
sell, hold
);
}
}
// The full starting state contains the final profit.
return dp[0][1][2];
}
};
// Driver code
int main() {
vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because there are N × 2 × 2 useful states, and each state performs constant-time transition work.

Space Complexity: O(N), where N is the number of days, because the dp array stores a constant set of ownership and transaction states for every day, while iterative evaluation uses no recursion stack.

Space Optimization

Tabulation reads only row index + 1 while building row index. Earlier rows and later completed rows never participate in the current transition, so the full dp table stores more history than necessary.

Two constant-sized tables are enough. Table next stores the following day's states, and table current receives the present day's states. After every day, shifting current into next prepares the same transitions for the preceding day.

Algorithm

  • Keep two 2 x 3 tables named next and current because every day depends only on the following day's ownership and transaction states.

  • Initialize next with zeros because the virtual day after the array cannot produce any profit.

  • Process days from right to left so next always contains every state required for the current day's choices.

  • Calculate each current buy state from buying or waiting because matching values in next already contain every possible future result.

  • Calculate each current held state from selling or holding, reducing the transaction count only for the sale transition.

  • Shift the fully calculated current table into next because the preceding day needs the present day as the following-day layer.

  • Return next[1][2] after day 0 because the final layer represents an empty portfolio with two sales available at the start.

Dry Run

best-time-to-buy-and-sell-stock-iii-space-optimization-state-key-fixed.png

best-time-to-buy-and-sell-stock-iii-space-optimization-state-key-fixed.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the largest profit from at most two trades.
int maxProfit(vector<int>& prices) {
int n = prices.size();
// Next stores the following day's trading states.
vector<vector<int>> next(2, vector<int>(3, 0));
// Backward order keeps the required future layer ready.
for (int index = n - 1; index >= 0; index--) {
// Current states use only the next day's answers.
vector<vector<int>> current(2, vector<int>(3, 0));
// Zero remaining trades stays at the base value.
for (
int remainingTransactions = 1;
remainingTransactions <= 2;
remainingTransactions++
) {
// Buying spends money before a later sale.
int buy = -prices[index]
+ next[0][remainingTransactions];
// Waiting preserves an empty portfolio.
int skip = next[1][remainingTransactions];
// Current buy state keeps the better choice.
current[1][remainingTransactions] = max(
buy, skip
);
// Selling earns money and completes one trade.
int sell = prices[index]
+ next[1][remainingTransactions - 1];
// Holding preserves the open position.
int hold = next[0][remainingTransactions];
// Current held state keeps the better choice.
current[0][remainingTransactions] = max(
sell, hold
);
}
// Shift current states into the next-day table.
next = current;
}
// The full starting state contains the final profit.
return next[1][2];
}
};
// Driver code
int main() {
vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because each day evaluates the four relevant ownership and transaction states with constant-time transitions.

Space Complexity: O(1), because two fixed 2 × 3 tables store only the current and next day's states, independent of N.

Interview follow-up Questions

Yes. An increasing array such as [1, 2, 3, 4] needs only one transaction for profit 3. The limit allows at most two transactions rather than requiring exactly two.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Input: nums = [1, 16, 7, 8, 4] Output: [1, 4, 8, 16] Explanation: Every pair inside [1, 4, 8, 16] satisfies the divisibility rule. The value 7 cannot join the chain because no other chain value div...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

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 t...

65.7k
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