Be the first user to complete this post

  • 0
 Add to List
Medium

558. Best Time to Buy and Sell Stocks II - Leetcode

Problem Statement

Given an integer array prices where prices[i] represents the price of a given stock on a day i, determine the maximum profit you can achieve.

On each day, you have the option to:

  • You can buy and/or sell the stock, but you can only hold one share at a time.
  • Buy and sell on the same day if it’s profitable.

Return the maximum profit you can achieve by capturing all profitable opportunities.

Example 1:

Input:  prices = [8, 2, 6, 3, 9, 4]
Output: 1
    Buy at 2 (Day 2) and sell at 6 (Day 3), for a profit of 4.
    Buy again at 3 (Day 4) and sell at 9 (Day 5), for a profit of 6.

Example 2:

Input:  prices = [1, 2, 3, 4, 5]
Output: 4
    Buy on day 1 (price = 1), sell on day 5 (price = 5), and profit = 4.

Example 3:

Input: prices = [5, 4, 3, 2, 1]
Output: 0
    Prices decline daily, so no transactions are made as no profit is possible.

To solve this problem, we need to maximize the profit by capturing all upward price movements between consecutive days. Instead of trying to figure out a specific buy-and-sell sequence, we simply capture every opportunity to make a profit if the price increases from one day to the next.

Approach

  1. Iterate through each day:
    • For each day i, check if the price on day i is lower than the price on day i+1.
    • If the price goes up, add the difference (prices[i+1] - prices[i]) to the profit.
  2. Calculate the total profit by summing up all positive differences between consecutive days.

This approach works because, for any sequence of price increases, the sum of individual day-to-day profits gives the maximum profit for that period.

Why Selling immediately works:

For prices = [1, 3, 5], here’s how to maximize profit:

  1. Day 1: Price = 1. Buy at 1.
  2. Day 2: Price rises to 3. Sell at 3, making a profit of 3−1=23 - 1 = 23−1=2.
  3. Day 2: Immediately buy again at 3.
  4. Day 3: Price rises to 5. Sell at 5, making a profit of 5−3=25 - 3 = 25−3=2.

So the total profit is:

  • First transaction: 2 (from buying at 1 and selling at 3)
  • Second transaction: 2 (from buying at 3 and selling at 5)

Total Profit = 2 + 2 = 4.

In this case, buying on Day 1 at price 1 and selling on Day 3 at price 5 yields the same total profit of 4.

The approach here is flexible:

  • We could take smaller, consecutive buys and sells (buy at 1, sell at 3, then buy at 3, sell at 5) for individual profits.
  • Or we could just buy once at the lowest price (Day 1) and sell at the highest price within the period (Day 3).

Both approaches give the same maximum profit when the prices steadily increase.

 

Output:

10

Reference: Leetcode

Related Problems: