给定股票报价最大化利润

1. Overview

In this tutorial, we’ll discuss the problem of finding the maximum profit by buying and selling a product at most times. We’ll present a naive approach and then improve it to obtain a better solution.

In the end, we’ll present a comparison between both approaches and when to use them.

2. Defining the Problem

Suppose we’re concerned with a product. We know the prices of this product over the next days in advance. The price of the $i^{th}$ day is denoted as P_i . Hence, we’re given an array called of size .

We’re allowed to make at most transactions, where a new transaction can only start after the previous transaction is complete. By a transaction, we mean the process of buying and selling the product.

We’re asked to find out the maximum profit we can obtain by planning our trading strategy optimally.

In other words, we need to choose at most pairs of indexes. For each pair, we buy the product on the first day and sell it the other day.

Therefore, we need to find the maximum value of:

$[\boldsymbol{\sum_{i=0}^{K-1}(P_{s_i} - P_{b_i})}]$

Such that $\boldsymbol{s_i \ge b_i}$ , where $\boldsymbol{s_i}$ is considered the selling day and $\boldsymbol{b_i}$ is considered the buying day.

3. Naive Approach

3.1. General Idea

Let’s start thinking about this problem, We have days. In each day, we might decide to buy the product. If we decided to buy a product, then we should choose a day after it to sell the product. We can keep doing this as long as the number of transactions doesn’t exceed times. Also, we must pay attention to that we don’t have any unsold products.

This problem can be easily solved using a dynamic programming approach.

At first, let’s define as the maximum profit we can get from the first days by performing transactions.

At the day , we have two choices:

Just skip it. Therefore, . Since we don’t do anything on this day, all the profits come from the days before it.
Sell a product that we bought before. In this case, we should select a buying day before this day. Thus, , where denotes the buying day. Since we bought the product on the day and then sold it on the day , we add to the profit. Also, we add to the profit because we can’t carry two or more unsold products.

3.2. Implementation

Take a look at the implementation of this approach:

algorithm DynamicProgrammingApproach(P, n, K):
    // INPUT
    //    P = The prices array
    //    n = The size of the prices array
    //    K = The maximum number of allowed transactions
    // OUTPUT
    //    Returns the maximum profit that can be achieved

    profit <- an empty 2D array with dimensions [n+1, K+1] initialized to 0
    
    for i <- 1 to n:
        for k <- 1 to K:
            max_so_far <- 0
            for j <- 1 to i:
                max_so_far <- max(max_so_far, P[i] - P[j] + profit[j-1, k-1])
            profit[i, k] <- max(profit[i-1, k], max_so_far)
    
    answer <- 0
    for k <- 1 to K:
        answer <- max(profit[n, k], answer)
    
    return answer

At first, we do some Initializations:

because there isn’t any profit from any number of days with transactions.
because there isn’t any profit from any number of transactions with days.

After that, we start to fill the dynamic programming array profit according to the equations mentioned above.

For each pair (, ), initially, we assume that we don’t want to sell on the day . Therefore, we consider profit[i-1][k] to be the maximum profit we can get from the first days if we use transactions. Then, we try to get a better profit by buying a product on the day and selling it on the day . Thus, we iterate over all possible and check if we can get a better profit.

Finally, we iterate over all possible number of transactions after days and take the one that gives us the maximum profit.

The complexity of this approach is $\boldsymbol{O(n^2 \times k)}$ , where is the number of days, and is the maximum number of allowed transactions.

4. Faster Approach

Let’s try to improve our naive approach.

4.1. General Idea

In the naive approach, we tried all possible buying days when we were calculating profit[i][k] . However, we can suffice with the day that makes profit[j-1][k-1] + P_i - P_j as maximum as possible. Hence, let’s think about how to get this maximum value for each pair (i,k) as fast as possible.

If we think deeply, we can show that we can solve this problem also by dynamic programming.

Since P_i is fixed for the current , let’s define an equation that holds all the changing variables:

$[\boldsymbol{maxProfit[i][k] \gets \max_{j \leq i}(profit[j-1][k-1] - P_j)}]$

We notice that we’re maximizing this value for each prefix of the array. If the prefix was [0, i - 1] , and we moved to the next prefix [0, i] , then the only element that is added to the range is the element i - 1 . Therefore, the maximum value will either stay the same as before or get updated with value .

As a result, we can calculate a prefix maximum for this value by using the following equation:

$[$\boldsymbol{maxProfit[i][k] \gets \max(profit[i-1][k-1] - P_i , maxProfit[i-1][k])}]$

Back to naive approach, the maximum profit was either from skipping the current day, or from selling the product on the day and finding the best day to buy it in. We can write an equation that summerizes this:

$[$\boldsymbol{profit[i][k] \gets \max(\max_{j \leq i} (profit[j-1][k-1] + P[i] - P[j]), profit[i-1][k])}]$

By taking advantage of the maxProfit equation, we can come to the final result:

$[$\boldsymbol{profit[i][k] \gets \max(maxProfit[i][k] + P[i], profit[i-1][k])}]$

Now that we found the final equation to use, we can jump into the implementation.

4.2. Implementation

Take a look at the implementation of the Faster approach:

algorithm FasterDynamicProgrammingApproach(P, n, K):
    // INPUT
    //    P = The prices array
    //    n = The size of the prices array
    //    K = The maximum number of allowed transactions
    // OUTPUT
    //    Returns the maximum profit that can be achieved

    profit <- an empty 2D array with dimensions [n+1, K+1] initialized to 0
    maxProfit <- an empty 2D array with dimensions [n+1, K+1] initialized to -infinity
    
    for i <- 1 to n:
        for k <- 1 to K:
            if i = 1:
                maxProfit[i, k] <- -P[i]
            else:
                maxProfit[i, k] <- max(maxProfit[i-1, k], profit[i-1, k-1] - P[i])
            
            profit[i, k] <- max(profit[i-1, k], P[i] + maxProfit[i, k])
    
    answer <- 0
    for k <- 1 to K:
        answer <- max(profit[n, k], answer)
    
    return answer

Same as the naive approach, we’ll do some Initializations:

: There isn’t any profit from any day with transactions.
: There isn’t any profit with any number of transactions from days.
$maxProfit[i][0] = -\infty$ : This is to prevent the algorithm from selling the product without buying it before. The reason is that we can’t sell anything with transactions.
$maxProfit[0][k] = -\infty$ . This is also to prevent the algorithm from selling the product without buying it first. The reason is that day doesn’t exist.

After that, we start to fill the dynamic arrays ( profit and maxProfit ) according to the equations mentioned above.

For each pair (, ), firstly, we should fill maxProfit[i][k] . We have two choices. Either we consider that we buy the product on the day , or we buy it before that.

Secondly, we should fill profit[i][k] . Similarly, we have two choices, as well. Either we consider that we sell the product on the day . As a result, we’ll get maxProfit[i][k] + P[i] . Otherwise, we don’t sell the product on this day.

Finally, we iterate over all possible number of transactions after days and take the one that gives us the maximum profit.

The complexity of this approach is $O(n \times k)$ , where is the number of days, and is the maximum number of allowed transactions.

5. Comparison

When considering the time complexity, the faster approach generally has a lower complexity.

However, in the particular case, when we care about memory complexity, using the naive approach should consume less memory. Generally speaking, the naive approach consumes approximately half the memory comparing to the faster method. The reason is that the faster approach contains the maxProfit array.

6. Conclusion

In this tutorial, we explained the problem of calculating the maximum profit from buying and selling a product at most times. Firstly, we presented the naive approach.

Secondly, we discussed the theoretical idea and the implementation of a faster approach.

Finally, we presented a summary comparison between both approaches and showed when to use each one.

Persistence

REST

Security