NUHMAN.com

Introduction

LeetCode 123: Best Time to Buy and Sell Stock III is a problem that builds upon the previous stock buy and sell problems. In this version, you are allowed to perform at most two transactions, meaning you can buy and sell a stock twice. The goal is to maximize your profit by choosing two distinct days to buy and sell the stock. This is a classic problem that requires dynamic programming to efficiently compute the maximum profit while taking into account the constraint of at most two transactions.

Problem Statement

You are given an array prices where prices[i] represents the price of the stock on the ith day. You can complete at most two transactions: one buy and one sell per transaction. Your task is to find the maximum profit you can achieve. If you cannot make any profit, return 0.

Example:

go

Input: prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6 - 2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3 - 0 = 3.
Total profit = 4 + 3 = 7.

Approach:

To solve the problem efficiently, we can use dynamic programming. The key idea is to maintain two states for each day:

1. buy1: The maximum profit that can be made if we have bought the stock once by the current day.
2. sell1: The maximum profit that can be made if we have sold the stock once by the current day.
3. buy2: The maximum profit that can be made if we have bought the stock twice by the current day.
4. sell2: The maximum profit that can be made if we have sold the stock twice by the current day.

Steps:

1. Start with initializing:

• buy1 as negative infinity (since we want to simulate buying, and we need to track the lowest price).
• sell1 as 0 (since no transaction has been made yet).
• buy2 as negative infinity (similar to buy1, it tracks the maximum profit from the second buy).
• sell2 as 0 (no second sale has been made).

1. For each price, update these four variables:

• buy1: The maximum of the current buy1 or the negation of the price (representing a buy action).
• sell1: The maximum of the current sell1 or buy1 + price (representing a sell after the first buy).
• buy2: The maximum of the current buy2 or sell1 - price (representing a buy after the first sell).
• sell2: The maximum of the current sell2 or buy2 + price (representing a sell after the second buy).

1. The result will be stored in sell2, which represents the maximum profit after completing two transactions.

Go Implementation

Solution Using Dynamic Programming

go

package main

import "fmt"

// maxProfit calculates the maximum profit that can be achieved
// by performing at most two transactions.
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    // Initialize variables
    buy1 := -prices[0]
    sell1 := 0
    buy2 := -prices[0]
    sell2 := 0

    // Iterate through the prices array
    for i := 1; i < len(prices); i++ {
        buy1 = max(buy1, -prices[i])            // Maximize the profit from the first buy
        sell1 = max(sell1, buy1 + prices[i])    // Maximize the profit from the first sell
        buy2 = max(buy2, sell1 - prices[i])     // Maximize the profit from the second buy
        sell2 = max(sell2, buy2 + prices[i])    // Maximize the profit from the second sell
    }

    return sell2 // The maximum profit after two transactions
}

// max is a helper function to find the maximum of two integers.
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    prices := []int{3, 2, 6, 5, 0, 3}
    result := maxProfit(prices)
    fmt.Println(result) // Output: 7
}

Explanation:

1. Initialization:

• We initialize buy1 and buy2 to negative infinity to represent that no stock has been bought yet.
• sell1 and sell2 are initialized to 0 since no transactions have been completed at the beginning.

1. Dynamic Programming Updates:

• We iterate through the prices array and update the values of buy1, sell1, buy2, and sell2 using the formulas derived from the greedy approach described earlier.
• After processing all the prices, the value of sell2 will contain the maximum profit achievable with at most two transactions.

1. Helper Function max:

• This function is used to compute the maximum of two integers, helping us update the values of buy1, sell1, buy2, and sell2.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Time Complexity:

• The time complexity is O(n), where n is the length of the prices array. We perform a single pass through the array, updating the four variables (buy1, sell1, buy2, sell2) as we go.

Space Complexity:

• The space complexity is O(1) because we are using a constant amount of extra space to store the variables.

Edge Cases

1. Edge Case: No Prices

• Input: []
• Output: 0
• Explanation: If the prices array is empty, no transactions can be made, and the profit is 0.

1. Edge Case: All Prices Are the Same

• Input: [5, 5, 5, 5, 5]
• Output: 0
• Explanation: If all the prices are the same, no profit can be made, so the result should be 0.

1. Edge Case: Prices Decrease Continuously

• Input: [7, 6, 4, 3, 1]
• Output: 0
• Explanation: If the prices are continuously decreasing, no profit can be made, so the result is 0.

1. Edge Case: Only One Price

• Input: [10]
• Output: 0
• Explanation: If there is only one price, no transaction can be made, so the profit is 0.

Conclusion

LeetCode 123: Best Time to Buy and Sell Stock III introduces the challenge of maximizing profit with at most two transactions. By using a dynamic programming approach with four key variables (buy1, sell1, buy2, and sell2), we efficiently track the potential profits through multiple transactions. The solution runs in O(n) time with O(1) space complexity, making it optimal for large inputs.