Back to Problems

Best Time to Buy and Sell Stock II

Medium
greedy

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Greedy Insight: Capture every upward price movement. If tomorrow's price is higher than today's, buy today and sell tomorrow. The sum of all positive differences equals the maximum profit.

Why Greedy Works: We can complete as many transactions as we want. Any profitable opportunity (price going up) should be captured. There's no penalty for multiple transactions, so we greedily take every gain.

Example 1

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

Example 2

Input: prices = [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. Alternatively, capture each daily gain: (2-1) + (3-2) + (4-3) + (5-4) = 4.

Example 3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: Prices only decrease, so no profitable transaction is possible. Maximum profit is 0.

Constraints

  • •1 <= prices.length <= 3 * 10^4
  • •0 <= prices[i] <= 10^4
Show Hints (4)
Hint 1: What happens when you sum up all the positive differences between consecutive days?
Hint 2: If price[i+1] > price[i], buying on day i and selling on day i+1 is always profitable.
Hint 3: Multiple small gains can be combined: buying at day 1 and selling at day 5 gives the same profit as capturing gains from days 1-2, 2-3, 3-4, and 4-5.
Hint 4: The greedy approach is: add profit whenever the next day's price is higher.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?