101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming with 2K States - Complex approach
  2. Dynamic Programming with 2D Arrays - Complex approach
  3. Optimized Dynamic Programming - Complex approach

Approach 1: Dynamic Programming with 2K States

The key insight for solving this problem is to use dynamic programming to track the maximum profit after different states of transactions.

Let's define two arrays:

  • buy[j]: Maximum profit after buying the j-th stock.
  • sell[j]: Maximum profit after selling the j-th stock.

For each day, we have the following state transitions:

  • buy[j] = max(buy[j], sell[j-1] - prices[i]): Either keep the previous state or buy the j-th stock using the profit from the (j-1)-th transaction.
  • sell[j] = max(sell[j], buy[j] + prices[i]): Either keep the previous state or sell the j-th stock.

At the end, sell[k] will represent the maximum profit after at most k transactions.

Note that when k is large (k >= n/2), the problem reduces to the Best Time to Buy and Sell Stock II problem, where we can make as many transactions as we want. In this case, we can use a greedy approach to maximize profit.

Algorithm:

  1. If k is 0 or the prices array is empty, return 0.
  2. If k is large (k >= n/2), use the greedy approach from Best Time to Buy and Sell Stock II.
  3. Initialize arrays buy and sell of size k+1.
  4. Set buy[j] = -prices[0] and sell[j] = 0 for all j from 1 to k.
  5. Iterate through the prices array starting from the second day (i = 1):
  6. a. For each j from 1 to k:
  7. i. Update buy[j] = max(buy[j], sell[j-1] - prices[i]).
  8. ii. Update sell[j] = max(sell[j], buy[j] + prices[i]).
  9. Return sell[k] as the maximum profit.

Time Complexity:

O(n*k)

Where n is the length of the prices array and k is the maximum number of transactions. We iterate through the array once, and for each day, we update k states.

Space Complexity:

O(k)

We use two arrays of size k+1 to store the maximum profit for each state.

Approach 2: Dynamic Programming with 2D Arrays

Another approach is to use dynamic programming with 2D arrays to track the maximum profit at each day for different numbers of transactions.

Let's define two 2D arrays:

  • buy[i][j]: Maximum profit after buying the j-th stock on day i.
  • sell[i][j]: Maximum profit after selling the j-th stock on day i.

For each day, we have the following state transitions:

  • buy[i][j] = max(buy[i-1][j], sell[i-1][j-1] - prices[i]): Either keep the previous state or buy the j-th stock using the profit from the (j-1)-th transaction.
  • sell[i][j] = max(sell[i-1][j], buy[i][j] + prices[i]): Either keep the previous state or sell the j-th stock.

At the end, sell[n-1][k] will represent the maximum profit after at most k transactions.

Algorithm:

  1. If k is 0 or the prices array is empty, return 0.
  2. If k is large (k >= n/2), use the greedy approach from Best Time to Buy and Sell Stock II.
  3. Initialize 2D arrays buy and sell of size n x (k+1).
  4. Set buy[0][j] = -prices[0] and sell[0][j] = 0 for all j from 1 to k.
  5. Iterate through the prices array starting from the second day (i = 1):
  6. a. For each j from 1 to k:
  7. i. Update buy[i][j] = max(buy[i-1][j], sell[i-1][j-1] - prices[i]).
  8. ii. Update sell[i][j] = max(sell[i-1][j], buy[i][j] + prices[i]).
  9. Return sell[n-1][k] as the maximum profit.

Time Complexity:

O(n*k)

Where n is the length of the prices array and k is the maximum number of transactions. We iterate through the array once, and for each day, we update k states.

Space Complexity:

O(n*k)

We use two 2D arrays of size n x (k+1) to store the maximum profit for each state at each day.

Approach 3: Optimized Dynamic Programming

We can optimize the space complexity of the dynamic programming approach by using 1D arrays instead of 2D arrays.

Since we only need the values from the previous day to calculate the values for the current day, we can use 1D arrays to track the maximum profit for each state.

This approach is essentially the same as the first approach, but it provides a different mental model for understanding the problem.

Algorithm:

  1. If k is 0 or the prices array is empty, return 0.
  2. If k is large (k >= n/2), use the greedy approach from Best Time to Buy and Sell Stock II.
  3. Initialize arrays buy and sell of size k+1.
  4. Set buy[j] = -prices[0] and sell[j] = 0 for all j from 1 to k.
  5. Iterate through the prices array starting from the second day (i = 1):
  6. a. For each j from 1 to k:
  7. i. Update buy[j] = max(buy[j], sell[j-1] - prices[i]).
  8. ii. Update sell[j] = max(sell[j], buy[j] + prices[i]).
  9. Return sell[k] as the maximum profit.

Time Complexity:

O(n*k)

Where n is the length of the prices array and k is the maximum number of transactions. We iterate through the array once, and for each day, we update k states.

Space Complexity:

O(k)

We use two arrays of size k+1 to store the maximum profit for each state.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function maxProfit(k, prices):
    n = length of prices
    if k == 0 or n == 0:
        return 0
 
    // If k is large, use the greedy approach
    if k >= n / 2:
        maxProfit = 0
        for i from 1 to n-1:
            if prices[i] > prices[i-1]:
                maxProfit += prices[i] - prices[i-1]
        return maxProfit
 
    // Initialize arrays
    buy = new array of size k+1, initialized with -infinity
    sell = new array of size k+1, initialized with 0
 
    // Set initial values
    for j from 1 to k:
        buy[j] = -prices[0]
 
    // Dynamic programming
    for i from 1 to n-1:
        for j from 1 to k:
            buy[j] = max(buy[j], sell[j-1] - prices[i])
            sell[j] = max(sell[j], buy[j] + prices[i])
 
    return sell[k]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone