Maximizing Profit for Given Stock Quotes | Baeldung on Computer Science

1. Overview

In this tutorial, we’ll discuss the problem of finding the maximum profit by buying and selling a product at most $K$ 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 $n$ days in advance. The price of the $i^{th}$ day is denoted as $P_i$ . Hence, we’re given an array called $P$ of size $n$ .

We’re allowed to make at most $K$ 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 $K$ 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 $n$ 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 $K$ 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 $profit[i][k]$ as the maximum profit we can get from the first $i$ days by performing $k$ transactions.

At the day $i$ , we have two choices:

Just skip it. Therefore, $profit[i][k] = profit[i-1][k]$ . 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, $profit[i][k] = profit[j-1][k-1] + P_i - P_j$ , where $j$ denotes the buying day. Since we bought the product on the day $j$ and then sold it on the day $i$ , we add $P_i - P_j$ to the profit. Also, we add $profit[j-1][k-1]$ 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:

$profit[i][0] = 0$ because there isn’t any profit from any number of days with $0$ transactions.
$profit[0][k] = 0$ because there isn’t any profit from any number of transactions with $0$ days.

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

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

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

The complexity of this approach is $\boldsymbol{O(n^2 \times k)}$ , where $n$ is the number of days, and $k$ 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 $i$ , 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 $i$ .

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 $i$ 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:

$profit[i][0] = 0$ : There isn’t any profit from any day with $0$ transactions.
$profit[0][k] = 0$ : There isn’t any profit with any number of transactions from $0$ 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 $0$ 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 $0$ doesn’t exist.

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

For each pair ( $i$ , $k$ ), firstly, we should fill $maxProfit[i][k]$ . We have two choices. Either we consider that we buy the product on the day $i$ , 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 $i$ . 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 $n$ days and take the one that gives us the maximum profit.

The complexity of this approach is $O(n \times k)$ , where $n$ is the number of days, and $k$ 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 $K$ 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.

Core Concepts

Operating Systems

Neural Networks

Graph Theory

Latex

Full Archive

About Baeldung