Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

What is this problem about?

The "Best Time to Buy and Sell Stock II interview question" is an extension of the classic single-transaction stock problem. In this version, you are still given an array of prices, but you are now allowed to complete as many transactions as you like (i.e., buy and sell a stock multiple times). The only restriction is that you must sell the stock before you can buy it again. Your goal is to find the maximum total profit.

Why is this asked in interviews?

Companies like Amazon, Google, and Meta ask the "Best Time to Buy and Sell Stock II coding problem" to test a candidate's ability to simplify a problem using a Greedy approach. While it looks like it might require complex dynamic programming, the optimal solution is surprisingly simple. It evaluates whether a candidate can recognize that "multiple transactions" just means capturing every positive price increase.

Algorithmic pattern used

This problem follows the Greedy and Peak-Valley patterns. The core insight is that you can capture every single upward price movement. If the price on Day 2 is higher than on Day 1, you "buy" on Day 1 and "sell" on Day 2. If it goes up again on Day 3, you "buy" on Day 2 and "sell" on Day 3. This is equivalent to buying on Day 1 and selling on Day 3.

1. Iterate through the prices from index 1 to $n-1$.
2. If prices[i] > prices[i-1], add the difference prices[i] - prices[i-1] to your total profit.
3. If the price goes down or stays the same, do nothing.

Example explanation

Prices: [7, 1, 5, 3, 6, 4]

• Day 1 to 2: 1 < 7. No profit.
• Day 2 to 3: 5 > 1. Profit = $5 - 1 = 4$. Total = 4.
• Day 3 to 4: 3 < 5. No profit.
• Day 4 to 5: 6 > 3. Profit = $6 - 3 = 3$. Total = $4 + 3 = 7$.
• Day 5 to 6: 4 < 6. No profit. Total Maximum Profit: 7.

Common mistakes candidates make

• Over-engineering with DP: Trying to write a complex $O(N^2)$ or $O(N)$ state-based DP when a simple greedy loop is enough.
• Forgetting the "one stock at a time" rule: Thinking they can buy on multiple days before selling. However, even if they could, the greedy approach would still yield the same maximum profit.
• Trying to find the "global" minimum and maximum: Missing out on smaller profits in between that add up to a larger total.

Interview preparation tip

Whenever a problem allows "unlimited" actions and asks for "maximum profit," always check if a Greedy approach works. If you can break the problem into independent, locally optimal choices (like capturing every price increase), Greedy is often the $O(N)$ winner.