#122

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock II

Maximize stock profit by using a greedy approach to buy and sell multiple times, with state transition dynamic programming.

array dynamic programming greedy

Problem Statement

You are given an array of stock prices where prices[i] represents the price of a stock on day i. You are allowed to buy and/or sell stock on any day, but you can hold at most one share of stock at a time. Your goal is to find the maximum profit you can achieve by completing as many transactions as you want, where each transaction involves buying and selling the stock. You can also buy and sell on the same day.

The task is to determine the optimal way to buy and sell the stock, which may involve multiple transactions, in order to maximize your profit. This problem can be solved using a greedy approach with state transition dynamic programming, which efficiently handles the buying and selling logic for multiple days, ensuring that the maximum profit is achieved.

Examples

Example 1

Input: prices = [7,1,5,3,6,4]

Output: 7

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. Total profit is 4 + 3 = 7.

Example 2

Input: prices = [1,2,3,4,5]

Output: 4

Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.

Example 3

Input: prices = [7,6,4,3,1]

Output: 0

There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

Solution Approach

Greedy Approach with State Transitions

The greedy approach is used here by iterating through the array and calculating profits. By always buying stock when prices are lower and selling when prices are higher, you maximize profit. This is achieved by comparing each day’s price with the next day’s price and calculating the difference. If the next day's price is higher, sell today; otherwise, wait until the price increases.

Dynamic Programming with State Transitions

Using dynamic programming, we track the state of the system as we move through the array. The key states are holding the stock or not holding it. A DP approach will store the maximum profit for each state (buy, sell, hold), transitioning between states when appropriate. This approach efficiently computes the maximum profit while handling multiple transactions.

Optimizing Space with Greedy Dynamic Programming

A space-efficient dynamic programming solution can be achieved by reducing the space complexity to O(1) by only storing the two most recent states: holding stock and not holding stock. Instead of storing the entire state history, we can update these two variables as we traverse the array. This optimization preserves the time complexity while minimizing memory usage.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the greedy approach is O(n), where n is the length of the array. The space complexity can be optimized to O(1) using state transition dynamic programming, as only two variables are needed to track profit states across all days.

What Interviewers Usually Probe

Do you understand how dynamic programming helps in tracking stock profits across multiple transactions?
Can you explain the trade-offs between using a greedy approach versus a dynamic programming approach for this problem?
Will you be able to optimize the space complexity while maintaining O(n) time complexity?

Common Pitfalls or Variants

Common pitfalls

Misunderstanding that buying and selling on the same day is allowed, which can affect your approach to maximizing profit.
Failing to handle cases where stock prices are in descending order, leading to zero profit.
Not considering space optimization in dynamic programming, which could lead to unnecessary space complexity when it could be reduced.

Follow-up variants

Best Time to Buy and Sell Stock III - A similar problem where you are limited to at most two transactions.
Best Time to Buy and Sell Stock IV - Involves limiting the number of transactions to k.
Best Time to Buy and Sell Stock I - A simpler version where only one transaction is allowed.

FAQ

What is the best approach for solving the Best Time to Buy and Sell Stock II problem?

The best approach is using dynamic programming with state transitions or a greedy approach to maximize profit. Both approaches handle multiple transactions efficiently.

How do you ensure the maximum profit in this problem?

By iterating through the prices, you can maximize profit by buying at lower prices and selling at higher ones, applying the greedy approach to track profit states.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of days. This ensures an efficient solution even for larger input sizes.

Can you buy and sell stock on the same day?

Yes, buying and selling stock on the same day is allowed, which can be crucial for maximizing profit in this problem.

What are some space optimizations for this problem?

By reducing the space complexity to O(1), you can achieve a space-efficient solution by storing only the two most recent profit states.

terminal

Solution

Solution 1: Greedy Algorithm

Starting from the second day, if the stock price is higher than the previous day, buy on the previous day and sell on the current day to make a profit. If the stock price is lower than the previous day, do not buy or sell. In other words, buy and sell on all rising trading days, and do not trade on all falling trading days. The final profit will be the maximum.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(max(0, b - a) for a, b in pairwise(prices))

Solution 2: Dynamic Programming

We define $f[i][j]$ as the maximum profit after trading on the $i$th day, where $j$ indicates whether we currently hold the stock. When holding the stock, $j=0$, and when not holding the stock, $j=1$. The initial state is $f[0][0]=-prices[0]$, and all other states are $0$.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(max(0, b - a) for a, b in pairwise(prices))

Solution 3: Dynamic Programming (Space Optimization)

We can find that in Solution 2, the state of the $i$th day is only related to the state of the $i-1$th day. Therefore, we can use only two variables to maintain the state of the $i-1$th day, thereby optimizing the space complexity to $O(1)$.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(max(0, b - a) for a, b in pairwise(prices))

Continue Practicing

#55 jump game #45 jump game ii #376 wiggle subsequence