NUHMAN.com

Introduction

LeetCode 188 asks you to determine the maximum profit you can achieve from at most k transactions in a series of stock prices. A transaction involves buying and then selling a stock, and the goal is to maximize the profit by choosing the best times to buy and sell, subject to the constraint that you can perform at most k transactions.

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day. You are also given an integer k representing the maximum number of transactions you can make. The task is to find the maximum profit you can achieve, where one transaction is defined as buying and then selling a stock.

Function Signature:

go

func maxProfit(k int, prices []int) int

Example 1:

go

k := 2
prices := []int{2,4,1}
result := maxProfit(k, prices)
fmt.Println(result) // Output: 2

Example 2:

go

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

Constraints:

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

Approach

The problem can be solved using a dynamic programming approach. Since we are allowed to make multiple transactions, the strategy is to maintain a table that tracks the maximum profit for different numbers of transactions and for each day.

Dynamic Programming Approach:

1. State Representation: Let dp[t][i] represent the maximum profit achievable by making at most t transactions on the ith day.

• t ranges from 0 to k (representing the number of transactions).
• i ranges from 0 to n-1 (representing the number of days in the prices array).

1. State Transition: For each day and for each transaction count t, the maximum profit can be either:

• Not making a transaction on the i-th day, i.e., dp[t][i-1].
• Selling the stock on the i-th day after buying it on any previous day, i.e., the maximum of dp[t-1][j] + prices[i] - prices[j] for all j < i.

1. To optimize the transition for calculating the best buy day for each transaction, we can maintain a variable that tracks the best difference between dp[t-1][j] - prices[j] for each j < i.
2. Base Cases:

• dp[0][i] = 0 for all i because no profit can be made if no transactions are allowed.
• dp[t][0] = 0 for all t because no profit can be made on the first day.

1. Final Result: The result is stored in dp[k][n-1], where k is the maximum number of transactions, and n-1 is the last day.

Time Complexity:

• O(k * n), where k is the number of transactions and n is the number of days. This is because we are iterating through the array of prices for each transaction.

Space Complexity:

• O(k * n), since we use a 2D array of size k * n to store the results.

Go Implementation

go

package main

import "fmt"

func maxProfit(k int, prices []int) int {
    n := len(prices)
    
    // If no prices or no transactions, return 0 profit
    if n == 0 || k == 0 {
        return 0
    }

    // If k is larger than half the number of days, then we can make unlimited transactions
    if k >= n/2 {
        return maxProfitUnlimited(prices)
    }

    // DP table: dp[t][i] represents the maximum profit with at most t transactions up to the i-th day
    dp := make([][]int, k+1)
    for i := 0; i <= k; i++ {
        dp[i] = make([]int, n)
    }

    // Iterate over each transaction number
    for t := 1; t <= k; t++ {
        // Variable to store the maximum value of dp[t-1][j] - prices[j]
        maxDiff := -prices[0]
        
        for i := 1; i < n; i++ {
            // Update dp[t][i] by considering not making any transaction or selling on the i-th day
            dp[t][i] = max(dp[t][i-1], prices[i] + maxDiff)
            // Update maxDiff for the next day
            maxDiff = max(maxDiff, dp[t-1][i] - prices[i])
        }
    }

    return dp[k][n-1]
}

// Helper function to calculate the maximum of two integers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// Helper function to calculate profit with unlimited transactions (useful if k >= n/2)
func maxProfitUnlimited(prices []int) int {
    n := len(prices)
    profit := 0
    for i := 1; i < n; i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}

func main() {
    // Test case 1
    k1 := 2
    prices1 := []int{2, 4, 1}
    result1 := maxProfit(k1, prices1)
    fmt.Println(result1) // Output: 2

    // Test case 2
    k2 := 2
    prices2 := []int{3, 2, 6, 5, 0, 3}
    result2 := maxProfit(k2, prices2)
    fmt.Println(result2) // Output: 7
}

Explanation of the Code:

1. maxProfit function:

• Base Case Check: If the prices array is empty or the number of transactions (k) is 0, no profit can be made, so return 0.
• Unlimited Transactions Case: If k is greater than or equal to half the number of days (n/2), we treat the problem as if there are no restrictions on the number of transactions. In this case, we use the helper function maxProfitUnlimited to solve the problem.
• DP Table: A 2D array dp is used where dp[t][i] represents the maximum profit achievable with at most t transactions by the ith day. We update this table by iterating over each transaction number and each day, using the state transitions explained earlier.
• MaxDiff Calculation: maxDiff keeps track of the maximum profit difference between the best prior transaction and the price at day i.

2. maxProfitUnlimited function:

• This function handles cases where the number of transactions k is effectively unlimited (when k >= n/2). It simply sums up all profitable trades (where a stock can be sold for a higher price than it was bought for).

3. Helper max function:

• This is a utility function to return the maximum of two integers, used for the state transitions in dynamic programming.

4. Main Function:

• The main function contains test cases where the function maxProfit is called with different inputs to check the correctness of the solution.

Example Walkthrough

Example 1:

Input: k = 2, prices = [2,4,1]

• We can buy on day 0 (price = 2) and sell on day 1 (price = 4), making a profit of 4 - 2 = 2.
• There are no further profitable transactions, so the maximum profit is 2.

Output: 2

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]

• We can buy on day 1 (price = 2) and sell on day 2 (price = 6), making a profit of 6 - 2 = 4.
• Then, we can buy on day 4 (price = 0) and sell on day 5 (price = 3), making a profit of 3 - 0 = 3.
• The total profit is 4 + 3 = 7.

Output: 7

Conclusion

LeetCode 188: Best Time to Buy and Sell Stock IV can be efficiently solved using a dynamic programming approach. The solution leverages a 2D table to track the maximum profit for different transaction counts and days. This method ensures optimal performance for large inputs.