# 122. Best Time to Buy and Sell Stock II
LeetCode Problem Link (opens new window)
Given an array where the i-th element represents the price of a given stock on day i.
Design an algorithm to calculate the maximum profit you can achieve. You can complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
- Input: [7,1,5,3,6,4]
- Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
- Input: [1,2,3,4,5]
- Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and then sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
- Input: [7,6,4,3,1]
- Output: 0 Explanation: In this case, no transaction is done and the maximum profit is 0.
Constraints:
- 1 <= prices.length <= 3 * 10^4
- 0 <= prices[i] <= 10^4
# Approach
We've explained this problem in the greedy algorithm section before: Greedy Algorithm: Best Time to Buy and Sell Stock II (opens new window), but this time we will delve into the dynamic programming solution in detail.
The only difference here compared to 121. Best Time to Buy and Sell Stock (opens new window) is that in this problem, you are allowed to buy and sell the stock multiple times (note that you can only hold one stock at a time, so you must sell before buying again).
In terms of the dynamic programming approach, the main distinction between this problem and 121. Best Time to Buy and Sell Stock (opens new window) lies in the recurrence relation, while other aspects remain the same.
Let's focus on the transition formulas in this explanation.
First, let's clarify the meaning of the dp array:
dp[i][0]represents the maximum cash after holding the stock on day i.dp[i][1]represents the maximum cash after not holding the stock on day i.
If you hold the stock on day i, i.e., dp[i][0], it can be deduced from two states:
- Holding the stock from day i-1, keeping the status quo, so the cash remains the same as yesterday's held stock cash, i.e.,
dp[i - 1][0]. - Buying the stock on day i, the cash is yesterday's non-holding stock cash minus today's stock price, i.e.,
dp[i - 1][1] - prices[i].
Note that the only difference from 121. Best Time to Buy and Sell Stock (opens new window) is when deriving dp[i][0], where buying stock on day i is considered.
In 121. Best Time to Buy and Sell Stock (opens new window), since the stock can only be bought and sold once, if you buy the stock, dp[i][0] will definitely be -prices[i].
However, in this problem, as the stock can be bought and sold multiple times, when buying on day i, there might be profits from previous transactions.
Thus, if you buy the stock on day i, dp[i][0] would be dp[i - 1][1] - prices[i].
Similarly, if you do not hold a stock on day i, i.e., dp[i][1], it can be deduced from two states as well:
- Not holding the stock from day i-1, keeping things as they are, so the cash remains the same as yesterday's non-holding stock cash, i.e.,
dp[i - 1][1]. - Selling the stock on day i, the cash obtained is today's stock price plus yesterday's cash from holding the stock, i.e.,
prices[i] + dp[i - 1][0].
Note this aligns perfectly with 121. Best Time to Buy and Sell Stock (opens new window) in logic, as selling stocks to gain profit is completely logical!
Code is as follows (note the annotation in the code highlighting the only difference from 121. Best Time to Buy and Sell Stock):
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(2, 0));
dp[0][0] -= prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // Note this is the only difference from 121. Best Time to Buy and Sell Stock.
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
- Time Complexity: O(n)
- Space Complexity: O(n)
You can see that the code for this problem is almost the same as 121. Best Time to Buy and Sell Stock (opens new window), with only one key difference:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
This is exactly because in this problem, stocks can be traded multiple times! Therefore, when buying stocks, there may be previous trading profits, i.e., dp[i - 1][1], so dp[i - 1][1] - prices[i].
If you understand this, you have a deeper understanding of these two problems.
Here I also provide a version using the rolling array, as shown in the C++ code below:
// Version 2
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(2, vector<int>(2)); // Note that only a 2 * 2 sized 2D array is allocated here
dp[0][0] -= prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
}
return dp[(len - 1) % 2][1];
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- Time Complexity: O(n)
- Space Complexity: O(1)
# Versions in Other Languages
# Java:
// Dynamic Programming
class Solution {
// Implementation 1: Two-dimensional array storage
// Store each day's holding and not holding status with dp[i][0] and dp[i][1] respectively.
// Time Complexity: O(n), Space Complexity: O(n)
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2]; // Create a 2-dimensional array to store states
dp[0][0] = 0; // Initial state
dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // Day i, not holding stocks
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // Day i, holding stocks
}
return dp[n - 1][0]; // Selling stocks yields higher profit than holding, hence take [0]
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// DP using 2*2 Array (there's also a more optimized version using a 1-dimensional rolling array below)
class Solution {
public int maxProfit(int[] prices) {
int dp[][] = new int [2][2];
//dp[i][0]: holding the stock
//dp[i][1]: not holding the stock
dp[0][0] = - prices[0];
dp[0][1] = 0;
for(int i = 1; i < prices.length; i++){
dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
}
return dp[(prices.length - 1) % 2][1];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Space Optimization
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int[2];
// 0 indicates holding, 1 indicates selling
dp[0] = -prices[0];
dp[1] = 0;
for(int i = 1; i <= prices.length; i++){
// Holding from the previous day; since transaction times are not limited, add previous profit when buying again
dp[0] = Math.max(dp[0], dp[1] - prices[i-1]);
// Selling from the previous day or selling today; if selling today, must hold first
dp[1] = Math.max(dp[1], dp[0] + prices[i-1]);
}
return dp[1];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Python:
Version 1:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) # Note this is the only difference from 121. Best Time to Buy and Sell Stock
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
return dp[-1][1]
2
3
4
5
6
7
8
9
10
Version 2:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(2)] # Note that only a 2 * 2 sized 2D array is allocated here
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i % 2][0] = max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i])
dp[i % 2][1] = max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] + prices[i])
return dp[(length-1) % 2][1]
2
3
4
5
6
7
8
9
10
# Go:
// Best Time to Buy and Sell Stock II - Dynamic Programming
// Time Complexity: O(n) Space Complexity: O(n)
func maxProfit(prices []int) int {
dp := make([][]int, len(prices))
status := make([]int, len(prices) * 2)
for i := range dp {
dp[i] = status[:2]
status = status[2:]
}
dp[0][0] = -prices[0]
for i := 1; i < len(prices); i++ {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
}
return dp[len(prices) - 1][1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Dynamic Programming Version Two - Rolling Array
func maxProfit(prices []int) int {
dp := [2][2]int{} // Note only a 2 * 2 sized 2D array is allocated here
dp[0][0] = -prices[0]
dp[0][1] = 0
for i := 1; i < len(prices); i++ {
dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i - 1) % 2][1] - prices[i])
dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i])
}
return dp[(len(prices)-1)%2][1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# JavaScript:
// Method 1: Dynamic Programming (using dp array)
const maxProfit = (prices) => {
let dp = Array.from(Array(prices.length), () => Array(2).fill(0));
// dp[i][0] represents the maximum profit on day i while holding a stock.
// dp[i][1] represents the maximum profit on day i while not holding a stock.
dp[0][0] = 0 - prices[0];
dp[0][1] = 0;
for(let i = 1; i < prices.length; i++) {
// If holding on day i: carry over the previous day's status or buy on day i.
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
// If not holding on day i: carry over the previous day's status or sell on day i.
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
}
return dp[prices.length -1][1];
};
// Method 2: Dynamic Programming (using rolling array)
const maxProfit = (prices) => {
// Rolling array
// have: Maximum profit while holding stock on day i; notHave: Maximum profit while not holding stock on day i
let n = prices.length,
have = -prices[0],
notHave = 0;
for (let i = 1; i < n; i++) {
have = Math.max(have, notHave - prices[i]);
notHave = Math.max(notHave, have + prices[i]);
}
// You ultimately want to sell the stock to maximize profit
return notHave;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# TypeScript:
Dynamic Programming
function maxProfit(prices: number[]): number {
/**
dp[i][0]: maximum profit on day i while holding a stock
dp[i][1]: maximum profit on day i while not holding a stock
*/
const length: number = prices.length;
if (length === 0) return 0;
const dp: number[][] = new Array(length).fill(0).map(_ => []);
dp[0] = [-prices[0], 0];
for (let i = 1; i < length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[length - 1][1];
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Greedy Approach
function maxProfit(prices: number[]): number {
let resProfit: number = 0;
for (let i = 1, length = prices.length; i < length; i++) {
if (prices[i] > prices[i - 1]) {
resProfit += prices[i] - prices[i - 1];
}
}
return resProfit;
};
2
3
4
5
6
7
8
9
# C#:
Greedy Approach
public class Solution
{
public int MaxProfit(int[] prices)
{
int res = 0;
for (int i = 1; i < prices.Length; i++)
res += Math.Max(0, prices[i] - prices[i-1]);
return res;
}
}
2
3
4
5
6
7
8
9
10
Dynamic Programming
public class Solution
{
public int MaxProfit(int[] prices)
{
int[] dp = new int[2];
dp[0] = -prices[0];
for (int i = 1; i < prices.Length; i++)
{
dp[0] = dp[0] > dp[1] - prices[i] ? dp[0] : dp[1] - prices[i];
dp[1] = dp[1] > dp[0] + prices[i] ? dp[1] : dp[0] + prices[i];
}
return dp[1];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# C:
Dynamic Programming
#define max(a, b) ((a) > (b) ? (a) : (b))
int maxProfit(int* prices, int pricesSize){
int **dp = malloc(sizeof (int *) * pricesSize);
for (int i = 0; i < pricesSize; ++i) {
dp[i] = malloc(sizeof (int ) * 2);
}
// 0 indicates holding the stock maximally, 1 indicates not holding maximally
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < pricesSize; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[pricesSize - 1][1];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Greedy
int maxProfit(int* prices, int pricesSize) {
if(pricesSize == 0){
return 0;
}
int result = 0;
for(int i = 1; i < pricesSize; i++){
// If today's stock price is higher than yesterday's, it indicates profit
if(prices[i] > prices[i - 1]){
result += prices[i] - prices[i - 1];
}
}
return result;
}
2
3
4
5
6
7
8
9
10
11
12
13
# Rust:
Greedy
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut result = 0;
for i in 1..prices.len() {
result += (prices[i] - prices[i - 1]).max(0);
}
result
}
}
2
3
4
5
6
7
8
9
Dynamic Programming
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut dp = vec![vec![0; 2]; prices.len()];
dp[0][0] = -prices[0];
for i in 1..prices.len() {
dp[i][0] = dp[i - 1][0].max(dp[i - 1][1] - prices[i]);
dp[i][1] = dp[i - 1][1].max(dp[i - 1][0] + prices[i]);
}
dp[prices.len() - 1][1]
}
}
2
3
4
5
6
7
8
9
10
11
Optimization
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut dp = vec![-prices[0], 0];
for p in prices {
dp[0] = dp[0].max(dp[1] - p);
dp[1] = dp[1].max(dp[0] + p);
}
dp[1]
}
}
2
3
4
5
6
7
8
9
10