122. Best Time to Buy and Sell Stock II

Edited by Charles

Medium · Python · Dynamic Programming

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Solution 1: DP

Step 1: Define DP array states

Original study notes follow, including intermediate snippets and earlier attempts.

Solution 1: DP

Step 1: Define DP array states

dp[i][0]: the max cash at Iteration (i) if we are currently holding the stock;

dp[i][1]: the max cash at Iteration (i) if we do not hold the stock;

Step 2: Recursive formula

dp[i][0] comes from two cases:

1. dp[i - 1][0]: the stock was held before Iteration (i - 1)
2. dp[i - 1][1] - prices[i]: the stock is bought at Iteration (i), and no share was held before Iteration (i).

dp[i][1] comes from two cases:

1. dp[i - 1][1]: nothing was done at Iteration (i - 1), i.e. no stock at the moment (i)
2. dp[i - 1][0] + prices[i]: stock was still held at Iteration (i - 1) and is sold at Iteration (i)

Step 3: Initial States

dp[0][0]: stock was held at the beginning, i.e. buying at Iteration (0), -prices[0]

dp[0][1]: stock was not held at the beginning, i.e. nothing done at Iteration (0), 0

Step 4: The order of Iteration: only one iteration over prices sequentially.

Step 5: Validate, given prices = [7, 1, 5, 3, 6 ,4]:

➡️ Initial State: dp[0][0] = -7 🆚 dp[0][1] = 0

➡️ Iteration 0/Step 1: dp[1][0] = max(dp[0][0], dp[0][1] - prices[1]) = -1 🆚 dp[1][1] = max(dp[0][1], dp[0][0] + prices[1]) = 0

➡️ Iteration 1/Step 2: dp[2][0] = max(dp[1][0], dp[1][1] - prices[2]) = -1 🆚 dp[2][1] = max(dp[1][1], dp[1][0] + prices[2]) = 4

➡️ Iteration 2/Step 3: dp[3][0] = max(dp[2][0], dp[2][1] - prices[3]) = 1 🆚

dp[3][1] = max(dp[2][1], dp[2][0] + prices[3]) = 4

➡️ Iteration 3/Step 4: dp[4][0] = max(dp[3][0], dp[3][1] - prices[4]) = 1 🆚

dp[4][1] = max(dp[3][1], dp[3][0] + prices[4]) = 7

➡️ Iteration 4/Step 5: dp[5][0] = max(dp[4][0], dp[4][1] - prices[5]) = 3 🆚

dp[5][1] = max(dp[4][1], dp[4][0] + prices[5]) = 7

Code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Initialize dp array and the states
        l = len(prices)
        if l == 0:
          return 0
        ##############################################
        dp = [[0] * 2 for _ in range(l)]
        ##############################################
        dp[0][0], dp[0][1] = -prices[0], 0
        # Iteration
        for i in range(1, l):
            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 the final result: no stock held at the end
        return dp[-1][1]

Solution 2: Caveat

Since we can buy and sell for multiple times and they can happen on the same day but the only constraint is only one share is allowed to hold, i.e. buy → sell or sell → buy, instead of buy → buy.

Code:

Study record

Field	Value
Attempts	2
Mastery	❚❚
The Latest Attempt	November 3, 2025
Feedback	Pay attention to multiple transaction is allowed but there has to be only one share at hand.

Python solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Initialize dp array and the states
        l = len(prices)
        if l == 0:
          return 0
        ##############################################
        max = 0

        for i in range(1, l):
            daily_profit = prices[i] - prices[i - 1]
            if daily_profit > 0:
                max += daily_profit

        return max

---

Back to Day 35 Dynamic Programming VIII · All Algorithm notes