Best Time to Buy and Sell Stock II: Unlimited Transactions

59.6k
0

An integer array prices contains the price of one stock on consecutive days. Any number of transactions may be completed, and each transaction contains one purchase followed by one sale.

Only one share may be held at a time, so a sale must occur before another purchase. Buying and selling on the same day is allowed. Return the maximum total profit, with zero profit allowed when no profitable transaction exists.

Example 1

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Buying at 1 and selling at 5 earns 4. Buying again at 3 and selling at 6 earns 3, producing total profit 7.

Example 2

Input: prices = [5]
Output: 0
Explanation: A single day cannot complete a profitable purchase-and-sale pair, so skipping every action keeps profit at 0.

Recursion

Every day offers one useful choice between acting and waiting. An empty hand allows a purchase or a skip, while a held share allows a sale or a hold. Both paths lead to the same smaller problem on the next day, so recursion can explore every valid trading sequence.

State solve(day, canBuy) stores the best profit available from day onward. Flag value 1 means no share is held, while flag value 0 means a sale must happen before another purchase. The public method starts with the initial call solve(0, 1) because trading begins on the first day with an empty hand.

Algorithm

  • Begin with solve(0, 1) because the trading period starts on day 0 without a held share.

  • Return 0 after the last day because no later transaction can add profit and every pending action may be skipped.

  • Explore a purchase by subtracting prices[day] and moving to canBuy = 0 because a held share blocks another purchase.

  • Explore a skip from canBuy = 1 without changing the state, since waiting preserves the right to purchase later.

  • Explore a sale by adding prices[day] and moving to canBuy = 1 because a completed sale permits another transaction.

  • Explore a hold from canBuy = 0 without changing the state because a later selling price may produce a larger profit.

  • Return the larger valid choice at every state because the best trading sequence must begin with one of the two available actions.

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 n = prices.size();
// No profit remains after the final day.
if (day == n) {
return 0;
}
// An empty hand allows buying or waiting.
if (canBuy == 1) {
// Buying pays the current stock price.
long long buy = -prices[day]
+ solve(day + 1, 0, prices);
// Skipping preserves the empty-hand state.
long long skip = solve(day + 1, 1, prices);
// The stronger opening choice maximizes profit.
return max(buy, skip);
}
// Selling collects the current stock price.
long long sell = prices[day]
+ solve(day + 1, 1, prices);
// Holding preserves the owned-share state.
long long hold = solve(day + 1, 0, prices);
// The stronger closing choice maximizes profit.
return max(sell, hold);
}
public:
// Finds the maximum profit from unlimited trades.
long long maxProfit(vector<int>& prices) {
// Trading starts empty-handed on the first day.
return solve(0, 1, prices);
}
};
// Driver code
int main() {
vector<int> prices = {7, 1, 5, 3, 6, 4};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

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

Complexity Analysis

Time Complexity: O(2N), where N is the number of days, because two choices can branch from each day in the worst-case recursion tree.

Space Complexity: O(N), because the deepest recursive path can contain one active call for each day.

Memoization

Recursive paths repeatedly reach the same pair of day and holding status. Recomputing an identical state cannot improve the answer, so a dp table can save every completed result and return cached profit during later visits.

The recursive choices and state meaning remain unchanged. Table entry dp[day][canBuy] stores the answer for one state, turning the exponential tree into a collection of at most two states per day.

Algorithm

  • Begin with a dp table of n rows and two columns filled with -1 because every valid state has a non-negative answer.

  • Start from solve(0, 1) because no share is held before the first trading day.

  • Return 0 after day n - 1 because no future action remains available.

  • Return dp[day][canBuy] when a stored value exists, preventing repeated evaluation of the same trading state.

  • Compare buying with skipping for canBuy = 1 because an empty hand permits either paying the current price or waiting.

  • Compare selling with holding for canBuy = 0 because a held share permits either collecting the current price or waiting.

  • Store and return the larger choice in dp[day][canBuy] so every later visit receives the best future profit immediately.

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,
vector<vector<long long>>& dp
) {
int n = prices.size();
// No profit remains after the final 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 buying or waiting.
if (canBuy == 1) {
// Buying pays the current stock price.
long long buy = -prices[day]
+ solve(day + 1, 0, prices, dp);
// Skipping preserves the empty-hand state.
long long skip = solve(day + 1, 1, prices, dp);
// The stronger opening choice enters the cache.
bestProfit = max(buy, skip);
} else {
// Selling collects the current stock price.
long long sell = prices[day]
+ solve(day + 1, 1, prices, dp);
// Holding preserves the owned-share state.
long long hold = solve(day + 1, 0, prices, 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 the maximum profit from unlimited trades.
long long maxProfit(vector<int>& prices) {
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, dp);
}
};
// Driver code
int main() {
vector<int> prices = {7, 1, 5, 3, 6, 4};
Solution obj;
cout << obj.maxProfit(prices);
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 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 or holding, because a held share blocks another purchase.

  • Preserve the same purchase subtraction and sale addition 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 II Tabulation

Best Time to Buy and Sell Stock II Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum profit with bottom-up states.
long long maxProfit(vector<int>& prices) {
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 or holding starts with an owned share.
long long sell = prices[day] + 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 = {7, 1, 5, 3, 6, 4};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because two constant-time states are filled 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 selling or holding so a sale reads aheadCanBuy and a hold reads aheadMustSell.

  • 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 II Space Optimization

Best Time to Buy and Sell Stock II Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum profit with rolling states.
long long maxProfit(vector<int>& prices) {
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
);
// The current sell state compares both choices.
long long currentMustSell = max(
prices[day] + 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 = {7, 1, 5, 3, 6, 4};
Solution obj;
cout << obj.maxProfit(prices);
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 replace the full dp table, and no recursion stack is used.

Interview follow-up Questions

No. Skipping every day produces profit 0, so decreasing or constant prices never force a loss.

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

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

55.1k
Comments0